접근 자체는 잘했는데, 중복해서 셀 수 있는 것을 놓쳐서 많이 헤맸다. 종만북 6.5장처럼 이러한 배열 문제에서 중복을 피할 수 있는 가장 쉬운 방법은 조건을 만족하는 것 중 가장 왼쪽 상단을 잡는 방향으로 진행하는 것이다. (이 지점을 놓친 것에 대해서 매우 반성하도록 하자.) 일단 문제 접근 방법은 다음과 같다. 1. 퀸의 공격 방향은 상하좌우대각이다. 2. 행, 열, 대각 성분을 따로 DP형태로 저장해놓는다. 퀸의 공격 성질을 감안해보면 각 행, 열, 대각 성분에 1개씩만 들어갈 수 있다는 것과 동치이기 떄문이다. 3, 반복적으로 비어있는 최초의 행을 찾고 그것을 기준으로 어떠한 열에 넣을 수 있는지를 기준으로 분할하여 계산한다. (실질적으로 함수 내부에서 N^2이라고 생각하기 쉬우나 실질적으로는 ..

처음에 접근한 방식은 다음과 같다. # 처음에 접근한 방법 일단 문제를 이해하면 전체 트리의 부분 트리 중 원소의 갯수가 K인 것의 갯수를 구하라는 것과 동치라는 사실을 쉽게 이해할 수 있다. 또한 트리라는 것을 감안할 때 DFS를 이용하여 루트가 밑쪽에 위치한 트리의 원소의 갯수를 활용하여 루트가 위쪽에 위치한 트리의 원소의 갯수를 도출시킬 수 있다는 사실을 파악하였다. 따라서 이러한 속성을 활용하여 dp[i][j]를 i를 Root node로 하고 해당 트리에 속한 원소의 갯수가 j를 만족하는 갯수라고 설정하였다. 이를 바탕으로 DFS를 타고 위로 올라가면서 점화식을 도출하려고 시도하였다. 다만 이 방법의 문제는 점화식을 세우는 것에 무리가 많다는 점이다. dp[i][j]를 구하기 위해서는 i 노드의 ..

접근 방법은 다음과 같다. dp[i][j]를 i번째 자리일 때, j만큼의 1을 가지고 있는 갯수라고 잡았다. 따라서 해당 DP의 점화식을 dp[i][j] = sigma(dp[i - k][j - 1]) ( 1 > L >> check_num; memset(dp, 0, sizeof(dp)); int result_store[32] = {0}; dp_check(1); ll sum_store[32]; // 각 자리기준 몇개가 존재하는지 int check_count = 0; while(check_num){ for(int i = 1; i

좀 애먹기는 했다.. 처음에는 백준 12865번 소풍처럼 메모리를 기준으로 구획하려고 하였는데 메모리 초과가 되었다. 생각해보면 당연한 결과인게 dp[10000000]을 하고 숫자를 넣게되면 128mb는 금방 넘게 된다. 그래서 다양한 풀이방법을 고안하게 되었고 해당 접근 방법은 다음과 같다. 메모리를 쓸건지 말건지 2가지 케이스가 존재한다. 그리고 이전에 메모리 상태에 따라서 사용 여부의 효율성이 결정난다. 즉 이러한 측면에서 부분문제를 해결함으로써 전체 문제의 답에 접근하는 최적 부분 구조(Optimal substructure) 형태임을 파악했어야 한다. 다만, 탐욕적으로 선택하는 방향은 아니므로 그리디가 아닌 DP(동적 계획법)으로 접근했어야 한다. 다만, 착각하기 쉬운 지점이 총 앱의 갯수가 N이..

처음에 진짜 개똥짓해서 어마어마하게 디버깅하고, 어마어마하게 고민한 문제이다. 처음 세웠던 논리는 다음과 같다. 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개의 상금을 포기한다면 최대한 상금이 큰 것을 포기하는 것이 유리할 것이다. 단, 해당 경기를 포기하였을 때, 상금 상한을 넘을 수 있는지를 체크해서 가능해야 한다. 즉, 이 과정을 수행하기 위해 판단 당시에 위치한 대회의 상금의 값과 이전까지의 상금들 중 최댓값을 비교해서 만약 해당 대회의 상금의 값이 크면 ..