나 요리학원 출신임

그리디로 풀 수있는 문제다 내가 움직일 수 있는 거리는 (손님 방문시간 - 현재시간)만큼이다 그럼 우린 시간순으로 정렬을하고 내가 움직일 수 있는 범위를 가지고 다니면서 만약 그 범위안에 손님이 만족하는 온도가 없다면 NO 가능하다면 YES를 출력해 줄 수 있따! 그리고 만족한다면 시간을 바꿔주고 왼쪽 오른쪽 범위는 각각 포함할 수 있는 최대, 최소의 거리로 해줘야한다 처음에는 만족하는 범위를 찾으려고 하다가 거꾸로 해야 쉽겠다 싶어서 주석처리하고 반대의 경우를 찾았다! 앞으로도 쉬운것좀 생각하자.. 어려운 방법말고..!! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 3..

주어지는 문자열들을 통해 만들수 있는 가장 긴 팰린드롬의 길이와 팰린드롬을 출력한다! 나는 map과 set을 이용해서 풀었다 먼저 set에 담는데 뒤집어서 같은 문자열이 있다며 팰린드롬의 짝이 된다 그래서 만약 뒤집어서 있다면 뒤집은 문자열의 카운트만 증가시켜주고 없다면 set에 넣어준다 그리고 set을 돌아보면서 각 문자열의 /2만큼은 기본적으로 붙일 수 있으므로 답에 추가하자! 그리고 만약 개수가 1인것중에 팰린드롬인것이 있다면 그것을 답의 중간에 붙여주자! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include using ..

이분탐색을 통해 값을 찾으려고했는데 계속 실패했다! 한번 생각해보자.. 이 문제에서는 인접한 수의 차를 최소로 하고싶고 그때의 k를 구하고싶다 그럴때는..! -1과 인접한 숫자들 중 최소와 최대의 평군이 최적이된다 문제를 풀면서는 생각못했는데 -1 옆에없는 수는 무시하는게 맞다 -1 옆에 있을때만 의미가 있으니까 근처에 있는 수를 찾아서 평균값을 구하고 대체해준다 그리고 n만큼 보면서 가장 큰 diff값을 찾으면 된다! ㅠㅠ 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include using namespace std; #define ll long long const int SIZE = 1e5+5; int..

dfs를 이용한 cycle 체크 문제 응용 만약 cycle이 있다면 NO이다 하지만 몇가지 조건이 더 있다 먼저 각 정점마다 최대 2개의 간선을 가지므로 indgree가 2보다 크면 fail 또한 cycle을 확인할 때 set을 통해 이미 본 간선은 지워준다고 생각하고 푼다 출력하는건 indgree가 낮은곳부터 쭉 dfs를 통해 출력하고 남은걸 출력하면 된다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67..

이분탐색으로 해결할 수 있는 문제다 mid일만큼 본다고 하면 mid/(g+b)만큼 g or b를 볼 수 있다 그럼 g*(mid/(g+b))만큼 좋은 날을 볼 수 있고 그 다음 볼수있는 날도 최대 g만큼 좋은날이다 결국 답은 g*(mid/(g+b))+min(mid/(g+b),g)로 나온다!! 근데 문제를 잘 보면 전체 도로를 어쨌든 공사는 해야하므로 최소 n일은 봐야한다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include #include using namespace std; #define ll long long ll n, g, b; bool solve(ll mid) {..

DFS+ 그리디를 이용해서 풀 수 있다 우선 지나간 길은 지나갈 수 없으므로 길을 지나갈 때 마다 x로 바꿔주자 그리고 우리가 봐야할 방향은 위부터 봐야 아래 남아있는 정점에 대해 이득이다 따라서 위부터 아래로 시작점에서 dfs를 돌리며 끝까지 가는지 체크를 해보자! 문제의 핵심은 dfs를 조금 변형하는 부분에 있다고 생각한다 내가 만약 x행의 끝부분까지 간다면 true를 리턴해주면 된다! 아니라면 false~~! 결국 도착하는 사람들은 true를 통해 갈 수 있다고 답을 알려준다...! dfs 열공하자 소스코드 (C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 ..

그리디 문제다 정렬을 시키고 뒤에 화학물질부터 보면된다 냉장고의 (x,y)라고 할 때 y를 기준으로 잡고 다음 화학물질의 x가 현재 y를 넘는지 안넘는지로 판단할 수 있다 넘는다면 같은 냉장고안에 넣을 수 있다 그리고 y값은 더 뒤에있는 값으로 초기화해준다 그리고 범위를 안넘으면 냉장고를 늘려주면 된다! 자바는 pair가 없어서 구현해야한다..! 그리고 pq는 minheap이다!! JAVA 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 import java.ut..

이진트리로 주어진 사칙연산이 유효한지 출력하는 문제다 입력이 조금 복잡하게 들어오는거 빼고는 크게 어렵지는 않은 문제다! 문제의 조건을 생각해보면 내가 현재 노드가 숫자일 때, 연산자일 때 나눠보면 된다 1. 숫자일 때 => 자식을 가지고 있으면 무조건 false다 2. 연산자라면 => 내 자식 두명을 재귀타고가서 둘다 참이라면 true다 코드가 좀 헷갈릴 수 있지만 재귀적으로 생각하면 쉽게 풀 수 있다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 import java.util.*; import java.io.*; public class So..

그리디로 풀 수 있는문제라고 해야할까?! 서로 겹치는 부분이 있다면 방에 갈 수 없다 문제를 풀기 위해서는 뒤부터 보자! 나는 pq를 사용했다 내가 더 뒤에있는 사람부터 보면서 구간을 [a,b]라고해보자 그럼 나의 뒤에있는 사람은 [a`,b`]라고 할 때 1) 갈 수 있는경우 a`b 이 때는 구간이 겹친다 따라서 a`를 저장해뒀다가 다시 pq에 넣어두자 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include #include using namespace std; int n, t; int main() { scanf(" %d", &t); for (int tc = 1..

문제를 이해하는데 오래걸렸던 문제다 야구를 하는데 총 N 이닝동안 진행을 하고 나는 선수들이 어떻게 공을 치는지 알고있다 내가 할 일은 순서만 정해주는 것이다! 여기서 조건은 1번타자는 무조건 4번째에 쳐야하고 이닝이 끝났을 때 이전 이닝에 마지막으로 친 타자 다음 타자부터 시작하고 아웃이 3번 된다면 해당 이닝이 끝난다는것! 구현자체는 어렵지 않은데 엄청 헷갈렸다 특히 점수를 매기는 과정에서 나는 배열을 만들어서 구현했는데 이 부분에서 내 앞의 3타자에게 점수를 줄 때는 답이안나왔고 내 뒤에 3타자로부터 점수를 받을 때는 답이 나왔다..! 구현 실수같은데 왜 그런지는 못 찾았다 어쨌든 문제를 풀어본다면! 먼저 순서를 정해야 하므로 next_permutation을 쓴다! 근데 이 때 order[0] = ..