백준 9095번 1,2,3 더하기 C++

 

1. 문제 설명

정수 4를 1,2,3의 합으로 나타내는 방법은 7가지가 있다.

정수 N이 주어졌을 때, 1,2,3의 합으로 나타내는 경우의 수를 구해라

 

dp 문제로 점화식(규칙)을 찾아서 풀이한다,

n이 1인 경우는 1개

n이 2인 경우는 2개

n이 3인 경우는 4개이고

n이 4인 경우    7개이다.

n이 5인 경우    13개

n이 6인 경우    24개

n이 7이면        44개

 

규칙을 보면

number[i] = number[i-1] + number[i -2] + number[i -3] 이라는 것을 알 수 있다.

이를 바탕으로 코드를 구현해 정답을 구한다.