Save my data

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

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