처음에 진짜 개똥짓해서 어마어마하게 디버깅하고, 어마어마하게 고민한 문제이다. 처음 세웠던 논리는 다음과 같다. 1. 맨 뒤부터 시작하여 해당하는 숫자보다 더 왼쪽에 있는 숫자가 만약 더 크게 되면 그 숫자는 절대로 같은 큐상에 위치할 수 없다. 2. 이를 활용하여 각 index별로 위치할 수 있는 큐의 갯수를 찾고 만약 0이라면 NO를 출력하면 된다. 혹은 1. 맨 앞부터 시작하여 해당하는 숫자보다 더 오른쪽에 있는 숫자가 만약 더 작데 되면 그 숫자는 절대로 같은 큐상에 위치할 수 없다. 2. 이를 활용하여 각 index별로 위치할 수 있는 큐의 갯수를 찾고 만약 0이라면 NO를 출력하면 된다. 특히 이 방법을 시도하면서 착각하였던 부분이 후자의 접근 방법의 경우 만약 오른쪽에 있는 숫자가 더 큰 것..

상당히 어려운 문제이다. DP의 트리에서의 이용이라고 할 수 있겠다. 푸는 느낌을 잘 기억해두도록 하자. 접근 방법 1. 각 Root가 진행될 수 있는 나아갈 수 있는 방향은 우수방향으로 선택되거나 선택되지 않는 2가지 방향밖에 없다. 2. 그런데, 문제 조건을 보면 각 연결된 노드끼리 동시에 우수마을이 될 수 없으므로 각 root가 진행될 수 있는 방향은 독립적인 것이 아닌 종속적이다. 3. 이때 종속시키는 기준이 필요하므로 아래를 기준으로 위를 채우는 방향으로 진행하면 된다. # Case 1 : Root를 선택하는 방향 이 케이스의 경우는 Sub node가 무조건 선택되지 않으면 된다. # Case 2 : Root를 선택하지 않는 방향 이 케이스의 경우는 Sub node가 선택되거나 선택되지 않는 것..

DP를 활용한 문제이다. 동적 계획법을 활용한 문제는 메모이제이션(Memoization)을 활용하여 반복되는 계산을 줄이고 완전탐색을 할 것인지 구조를 잡는 것이다. 이 문제에서 i번째 물건까지를 handling하면서 총 V의 부피를 할당했다고 했을 때 max value를 저장해두면 dp[i][j] = dp[i -1, j] 와 dp[i - 1, j - i번째 부피] + i번째 value 중 최댓값을 저장해두면 된다. (특히 array의 index와 정보를 매칭하는 아이디어는 잘 기억해두도록 하자.) 즉, 전후 참조하는 것이 아니라 index가 더 낮은 부분만을 참고하면서 위로 올라가는 형태이므로 DP로 처리하기에 적합하다. 단, 이 문제에서 주의할 지점은 가장 Base case에 대한 처리인데 맨 바닥은..

상당히 애먹은 문제이다... 전체적인 접근 방법은 다음과 같다. 1. 순차적으로 기존 상금의 합과 상금 상한을 비교한다. 2. 만약 상금의 합이 상금 상한을 넘는다는 의미는 해당 경기를 포기하거나, 적어도 앞의 경기 중 하나를 포기해야한다는 의미이다. (즉, 이 지점을 기준으로 적어도 앞 부분에 1개의 시합을 포기해야한다는 의미와 동치이다.) 3. 이때, 상금의 합이 작을 수록 유리하다. 그러면 1개의 상금을 포기한다면 최대한 상금이 큰 것을 포기하는 것이 유리할 것이다. 단, 해당 경기를 포기하였을 때, 상금 상한을 넘을 수 있는지를 체크해서 가능해야 한다. 즉, 이 과정을 수행하기 위해 판단 당시에 위치한 대회의 상금의 값과 이전까지의 상금들 중 최댓값을 비교해서 만약 해당 대회의 상금의 값이 크면 ..

어렵지는 않은 문제이다. 풀이방법은 다음과 같다. 1. Compare array에서 1을 가장 최우선적으로 체크한다. (1은 바로 0으로 만들면 연산을 아얘 안할 수 있개 때문이다.) 2. 0과 1이 아닌 원소를 고려하되, 짝수 홀수를 판단하여 홀수면 1개 줄이고 2로 나눠준다. (홀수라는 것은 해당 단계에서 +1을 해줬다는 의미이다. 왜냐하면 만약 그렇지 않다면 x2되어 짝수가 나오게 된다.) 위의 내용을 보면 그리디 알고리즘이라는 것을 인식해야 한다. 부분적으로 1. 1을 찾는다. 2. 0과 1이 아닌 수 중에 홀수면 -1시키고, 짝수면 그대로 납둔 상태에서 1/2시킨다. 3. 변경된 숫자들을 가지고 1, 2 과정을 반복한다. 즉, 초기 compare array에서 최적해를 다시 1, 2 과정으로 다..

일단 풀이방법을 다음과 같이 잡았다. 1.포션은 최대 체력의 절반 이하일때 섭취 (이때, 포션은 최대 절반만큼만 회복가능하므로 최대 HP를 넘어감으로써 손실량은 존재하지 않음) 2.위의 1번 결과에 의하여, 이길 방법이 존재하지 않는 경우는 초기 HP와 포션에 의한 총 회복량의 합이 싸움으로 인해 감소되는 HP보다 작을 때 발생 3.플레이어가 남을 때까지, 해당 플레이어의 공격을 빼고 절반 이하의 HP가 남을 경우 포션을 먹는 행위 반복(만약 포션이 없는 경우는 그대로 진행) 제일 중요한 접근 방법은 최대 절반을 기준으로 현재 HP의 Status를 판단하는 것이다. 포션을 절반보다 더 떨어졌을 때만 섭취하게 되면 Max_hp를 넘어갈 일이 존재하지 않으므로, 초반에 포션에 의한 HP증가량과 싸움에 의한 ..

1967과 동일한 알고리즘으로 접근해주면 된다. 구현 방법에 대해서 잘 기억해두도록 하자. #include #include #include #include using namespace std; struct node{ vector len_store; }; int visited[100001] = {0}; int end_point; int result; void tree_checker(node *data_store, int start, int length){ if(visited[start] != 0) return; visited[start] = 1; if(result < length){ end_point = start; result = length; } for(int i = 0; i < data_store[s..

종만북에서 본 적이 있는 유형이라 쉽게 푼 편이다. 이분트리 탐색의 경우에는 재귀를 활용해줘서 처리해주면 된다. 부분과 전체를 보면서 코드를 구현할 수 있어야 한다. 이 문제를 요약하면 전위 순회를 후위 순회로 돌려야하는 것이다. 이분트리를 보면 각 노드를 기준으로 왼쪽은 자신보다 더 작고, 오른쪽은 자신보다 크다. 이러한 성질은 전체적으로 보아도 성립하고 최소 단위로 보아도 성립한다. 즉, 전위 순회를 한 데이터를 기준으로 자신보다 큰 숫자가 나올 때 그것이 오른쪽 노드의 시작을 의미함을 이해할 수 있다. 그러므로 자신보다 큰 숫자가 어느 시점에 나오는지를 확인하고 그것을 기준으로 왼쪽과 오른쪽 노드를 구분하면 된다. 후위 순회의 경우, 이 과정에서 자식 노드의 왼쪽과 오른쪽을 출력하고 자기자신을 출력..