★★☆☆☆
멍하니 풀다가 제출해봤는데 정답처리가 됐다..
찾아보니 다 나처럼 풀었음
for문을 3개나 쓴다고..? 2개만 쓸 수 있을 것 같은데...
<나의 풀이>
우선 전형적인 dp문제이므로, 4와 5의 예시를 생각하면서,
5의 경우의 수를 구하는 데 4의 경우의 수를 어떻게 활용할 수 있을지 고민했다.
그 결과, 어떠한 임의의 한 숫자를 고정하고 나머지 숫자들을 k-1개의 정수로 표현하는 방법이 떠올랐다.
즉, 5는 1+4, 2+3의 합으로 나타내지는데, 1과 2를 고정하면 4과 3을 k-1개로 표현한 경우의 수만 더해주면 된다는 것이다.
따라서, dp[i][p]+=dp[j][p-1]
정답을 출력하기 위해서 10000000으로 나누어주는 것도 잊지 않았다.
<다른 사람의 풀이>
이번에는 다른 사람들과의 알고리즘에 차이가 없었다. (배열의 행과 열이 바뀌는 정도?)
그 중에서, 배열을 long long 타입으로 선언해주는 경우가 있던데,
나의 경우에는 dp값을 계산하는 과정에서 대입 전에 미리 나누어줌으로써
int 값을 초과하는 일이 발생하지 않아, int 배열을 써도 문제가 없었다.
long long 배열이 더 많은 메모리를 차지하므로 이 편이 더 좋아보인다.
https://github.com/jeongopo/DaliyCodeCpp/commit/ba457d7924f75f57c25815be199a8f1a1606671b
일단 시작하기