BOJ_9095_1,2,3_더하기

문제 보기

n이라는 정수가 주어진다. n은 양수이며 11보다 작다. n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 출력해야 하며 n이 3일 경우 1+2와 2+1의 경우의 수를 다른 경우의 수로 취급한다.

문제 이해

해당 문제는 n의 범위가 적기 때문에 전체 탐색으로 진행하여도 상관없다. 하지만 n의 범위가 100 ~ 1000이 넘어가게 될 경우 경우의 수가 기하 급수적으로 증가하게 된다. n의 크기가 크더라도 항상 풀수있는 DP 방식으로 문제를 해결해보자.

문제 풀이

우선 첫 번째 수 부터 차례대로 생각해보자.

• 1이 n일 경우
  • 1
• 2가 n일 경우
  • 1 + 1
  • 2
• 3가 n일 경우
  • 1 + 1 + 1
  • 1 + 2
  • 2 + 1
  • 3

값이 4이상일 경우, 마지막에 1일 경우 2일 경우 3일 경우로 나눠서 생각해보자 이렇게 나눠서 생각해보는 이유는 n은 (1,2,3)의 합으로 이뤄져 있기 때문에 마지막이 1이 되는 경우의 수 2가 되는 경우의 수 3이 되는 경우의 수로 나눠서 생각해 볼 수 있다.

총합이 3 + 1	총합이 2 + 2	총합이 1 + 3
(1+1+1) + 1	(1+1)+2	1 + 3
(1+2) + 1	(2) + 2
(2+1) + 1
(3) + 1

4가 될 수 있는 경우의 수는 총 7가지이고 위 내용을 점화식으로 변경하면 아래와 같은 공식이 나타난다. 아래의 식은 arr 배열에 n이 i의 값이였을 때 1,2,3으로 나타낼 수 있는 경우의 수가 들어가 있다.

n의 값이 4 이상일 경우

arr[i] = arr[i-1] + arr[i-2] + arr[i-3]

아래 깃허브 링크로 알고리즘 초보에게 도움이 되는 정보를 얻을 수 있습니다.
https://github.com/KUPS-Study