[백준] 9095: 1, 2, 3 더하기

[jerrytrap]

문제 링크

문제 분석

• 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구한다.
• 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

풀이

• 문제에 있는 예시(4를 1, 2, 3의 합으로 나타내는 방법)를 살펴보면 다음과 같다.
  • (1) + 3 -> 1을 만들 수 있는 경우의 수에 3 더하기
  • (1 + 1) + 2, (2) + 2 -> 2를 만들 수 있는 경우의 수에 2 더하기
  • (1 + 1 + 1) + 1, (1 + 2) + 1, (2 + 1) + 1, (3) + 1 -> 3를 만들 수 있는 경우의 수에 1 더하기
• 정수 n을 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 a(n)이라고 하자. 이 때, a(n-1)에 1을 더하는 방법, a(n-2)에 2를 더하는 방법, a(n-3)에 3을 더하는 방법의 수를 모두 더하면, a(n)을 구할 수 있다. 즉, a(n) = a(n-1) + a(n-2) + a(n-3)으로 나타낼 수 있다.