Save my data

배낭 문제와 비슷한 원리로 풀리는 문제인데, 처음에 아이디어를 잘못 가져다가 고민을 하는 바람에 시간이 엄청 걸렸다. 한 번에 안 풀려서 방치하고 있다가 푸는데 거의 이틀이 걸렸다... 핵심 아이디어 : 내가 현재 몇 종류의 동전을 가지고 있다면, 그 때 그 동전들을 가지고 목표값을 만들 수 있는 모든 경우의 수를 저장하는 것 처음에 나는 dp에 경우의 수를 저장하지 않고 각 동전이 입력될 때 그것을 가지고 만들 수 있는 누적합 비슷하게 저장하려고 시도했었다. 그러기 위해서 dp 를 2차원 배열로 만들고 온갖 헛수고를 했는데, 다시 생각해보면 문제풀이를 시작한 극초반에 다양한 아이디어가 스쳐가던 중 배낭 알고리즘 활용하는 방법이 뇌리에 스쳤었는데 그것을 구체화하지 못했던 것이 아쉽게 느껴진다. 난 항상 ..

DP 문제이다. DP 문제는 반복의 맨 처음 단계에서 어떤 패턴을 찾으면 그 다음은 빠르게 풀린다. 그리고 항상 그걸 못 찾아서 문제다... 다만 확실히 DP 문제를 풀면 풀수록 뇌가 DP 화 되는 느낌이 있다. 나 같은 범재도 이런식으로 반복하면 그래도 요령이 생기는구나 싶어서 보람은 있었다. ※ 결국 노력과 반복이 답이다... 문제 풀이 아이디어 공유 : 줄 == 가로방향, 칸 == 세로방향 먼저 각 줄의 i 번째까지 누적합을 저장해 줄 dp 리스트를 만든다. 0 으로 마진을 두는게 편해서 인덱스 번호는 항상 1 부터 시작하게 만드는 편이다. 다른 사람들은 그렇게 안 한 사람도 있었다. 누적합의 패턴이 어떤지는 모르지만 여타 DP 문제가 그래왔듯 이번에도 비슷하겠거니 싶어서 일단 그렇게 만들었다. 2..

다이나믹 프로그래밍 알고리즘을 활용하는 문제이다. DP 문제는 기초가 되는 점화식을 정확하게 세우면 문제가 쉽게 풀리는데, 계속 머릿속으로만 코드를 구성하려고 애쓰다보니 문제가 잘 안풀렸다. 대략적인 흐름을 dp[4] 정도까지만 노트에 써보면서 흐름을 파악하니 어느 정도 윤곽이 나오는 것을 보고, 잘 안풀리는 문제가 있으면 머리로 애쓸것이 아니라 노트에 써가면서 눈으로 흐름을 파악해야 된다는 것을 깨달았다. (나는 폰 노이만이 아니요) DP 문제에 대해 스스로 부족함을 많이 느끼고 있기 때문에 나 자신을 설명시킬 겸 최대한 상세하게 뜯어가면서 설명했다. 이번 문제에 대한 점화식의 유도 과정을 아래에 써보았다. 내가 현재 카드 한 개를 가지고 있다고 생각하는 것에서 출발해보자. 왜냐하면 한 개를 살 때의 ..