이 문제를 처음에 접했을 때는 어려움이 있었다. 그 이유는 다들 그렇겠지만 규칙 때문이다. 이 규칙이 DP유형이 덜 익숙하게 되면 조건을 걸고 풀어야하는 착각을 하게 된다. DP를 쓰는 이유를 알고 가면 더 쉬워진다. DP는 이미 계산 했던 것들을 계산하지 않고 가져다쓰는 일종의 캐시 개념으로 작동한다. 계산했던것을 몇번이고 다시 계산하면 당연히 느려질 수 밖에 없으니 이를 방지하는 기법이다. 그런데 DP를 사용하려면 중요한 점은 규칙을 찾아야 된다는 점이다. 피보나치수열과 같이 뒤로 1, 2번째 값을 더하는 간단한 것들은 바로 머리에 들어오는데 이 문제는 그렇지가 않다. 일단 규칙이 막 있으니까 조건걸어야되나? 싶게 보인다. 일단 딱보니 1차원 배열을 이용하면 될 것 같다. 그러면 먼저 1부터 시작해서..