Coding Test/백준
[C++/Python] 백준 9095 - 1, 2, 3 더하기
Junchoi
2020. 7. 23. 14:00
문제 링크
https://www.acmicpc.net/problem/9095
9095번: 1, 2, 3 더하기
문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는
www.acmicpc.net
N이 1일 때는 1, 2일 때는 2, 3일 때는 4가지 방법이 있습니다.
N이 4일 때는
3일 때에서 1씩 더하는 방법
2일 때에서 2씩 더하는 방법
1일 때에서 3씩 더하는 방법이 총 방법의 수 입니다.
N이 5일 때도 마찬가지로
N이 2, 3, 4일 때의 방법의 합과 같습니다.
따라서 N이 4 이상일 때에는 dp(N-1) + dp(N-2) + dp(N-3) 으로 구할 수 있습니다.
구현 코드