BOJ 2342 - Dance Dance Revolution (https://icpc.me/2342)
예전에 이 문제를 풀려다 실패하고, 마땅한 해법이 생각나지 않아서 포기한 적이 있다.
지금 생각해보면.. 그 당시의 나는 다음과 같은 문제점을 가지고 있었다.
- 어떤 것을 메모이제이션의 대상으로 삼아야할 지 감을 잡지 못했음
- 그런 이유로 이 문제를 매우 어려운 문제라고 착각함
DP 문제는, 항상 문제 내용에 제시하는 조건이나 단서가 있다.
메모이제이션의 대상으로 삼아야할 값이나, 상태나, 기타 등등..
그걸 어떤 식으로 기록하고 관리할 지 잘 고민해봐야 문제를 풀 수 있는 것 같다.
이 문제의 경우는 n번째 상황에서 가능한 경우를 모두 고려하고 그 시점에서의 최소값을 계속 저장하면서 올라가는 방식으로 해결할 수 있다.
정말 주의해야할 점은, 어느 특정 상황만을 고려하고 설계해서 처리해서는 안된다는 것이다.
내가 이렇게 설명하는게 맞는지는 모르겠지만, 이 문제의 특징이 있다면 ‘최초 상황을 제외하고는 두 발이 같은 위치에 있을 수 없으며, 발이 어느 위치에 있었냐에 따라 다음 스텝의 비용이 정해진다’는 것이다. 그렇기 때문에 이전에 내 발이 어디에 있었냐가 많은 영향을 주는데, 그 순간의 최적 케이스만 고려하고 나머지는 메모 안하고 갖다 버린다면 문제가 생긴다.
앞의 10번째 스텝까지는 이게 짱인거 같아서 그 상황만 잘 고려해서 저장해놨는데, 남아있는 15개 스텝을 진행해보니 앞의 10번째 스텝까지 조금 안좋게 진행했을때가 오히려 남은 15개 스텝을 최적값으로 진행할 수도 있기 때문이다.
10번째 스텝까지 제일 best였던 케이스가 있고, 제일 best하진 않은데 비용이 1 차이나는 케이스가 있었다고 치자.
11번째 스텝부터 25번째 스텝까지 계속 한발로 밟아야되는 케이스고, 후자 케이스의 경우 이미 한쪽 발을 거기에 올려져 있는 상태라 그대로 쭉 가면 되는데 전자 케이스가 그렇지 않아서 최종적으로 비용이 더 들 수도 있는 것이다.
그러므로 다음과 같이 설계해야된다.
D[i][j][k] -> D[5][5][N]
왼발은 i에, 오른발은 j에 머물러 있으면서 k번째 스텝까지 처리한 경우 최소값
참고로 첫 재시도에서는 이런식으로 설계했었다.
D[N][2][3] = N번째 스텝을 왼발로 밟았을 때의 최적값과 왼발, 오른발의 위치
보기 좋게 틀렸다. 이런식으로 저장하면, ‘나중에 가서야 최적값이 될 수 있는’ 케이스를 고려할 수 없다.
알고리즘 강의 듣고 열심히 문제 풀 때는 나름 DP에 대한 깨달음이 온 줄 알고 좋아했었는데, 실제로는 DP를 백 문제도 풀지 않았기 때문인지 설계하는데 있어서 실수를 많이 하는 것 같다. ㅠㅠ
여튼 설계를 했으면 어떤 식으로 저장할지 생각해서 for문을 작성하면 된다.
한가지 팁이 있다면 비용을 계산하는 메서드를 따로 만들면 편하다는 것이다.
요새 1주일에 DP 문제를 1~2개씩 정해서 풀고 있는데 나름 재밌어서 다행!