티스토리 뷰

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) 으로 구할 수 있습니다.

 

 

구현 코드

 

'Coding Test > 백준' 카테고리의 다른 글

[C++/Python] 백준 11057 - 오르막 수  (0) 2020.07.27
[C++/Python] 백준 10844 - 쉬운 계단 수  (0) 2020.07.24
[C++/Python] 백준 11727 - 2xn 타일링 2  (0) 2020.07.22
[C++/Python] 백준 11726 - 2xn 타일링  (0) 2020.07.21
[C++/Python] 백준 1463 - 1로 만들기  (0) 2020.07.20