접근 방법은 다음과 같다. 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이..

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