목록파이썬 15990번 (1)

하나씩 알아가기

[BOJ_15990] 1, 2, 3 더하기 5

문제를 해결하기 위한 점화식을 구하려면 2차원 dp를 만들어야 합니다. dp[n][1] = dp[n-1][2] + dp[n-1][3] dp[n][2] = dp[n-2][1] + dp[n-2][3] dp[n][3] = dp[n-3][1] + dp[n-3][2] n을 만들기 위한 방법의 수 중 1로 끝나는 경우를 dp[n][1]이라고 합시다. dp[n][1]은 ~~~ + 1 이런 식입니다. dp[n-1][?] 의 경우 1로 끝날 수 없기 때문에 2나 3이 올 수 밖에 없기 떄문에 dp[n][1] = dp[n-1][2] + dp[n-1][3]가 성립합니다. 그리고 dp[n][2]의 경우 주의해야 할 점은 ~~~ + 2로 끝났기 때문에 dp[n-2][?] 이 와야 한다는 점입니다. ※반복문 내부의 점화식에 %1..
알고리즘 2021. 1. 23. 21:16
이전 Prev 1 Next 다음