목록boj 9095 (1)

하나씩 알아가기

[BOJ_9095] 1, 2, 3 더하기

정수 n을 입력 받아서, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다. 1, 2, 3이라는 숫자가 고정이 되어 있습니다. 규칙을 찾아봅시다. n 1 2 3 4 5 경우의 수 1 2 4 7 ? 네번째 까지 구한 결과 f(1) + f(2) + f(3) = f(4)가 성립합니다 다섯번째 까지만 수동으로 구해봅시다 11111 1112 1121 1211 2111 122 212 221 113 131 311 23 32 총 13가지입니다. f(2) + f(3) + f(4) = f(5) 가 성립하므로 f(n) = f(n-3) + f(n-2) + f(n-1) 로 점화식을 도출할 수 있습니다. dp = [0 for _ in range(11)] dp[1] = 1 dp[2] = 2 dp[3] = 4 fo..
알고리즘 2021. 1. 22. 21:01
이전 Prev 1 Next 다음