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

문제 : 정수 n이 주어졌을 때, n 을 1,2,3 의 합으로 나타내는 방법의 수를 구하는 프로그램을 만들어라.

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

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

1+3

3+1

입력) 첫째줄에 테스트 개수 T 가 주어지고, 각 케이스는 1줄, 출력은 각 경우당 1줄 출력한다.

나는 이 문제를 동적 계획법으로 풀었다. 여러가지 해결법이 있었으나, 가장 합리적으로 보였다.

(동적 계획법이란, 문제를 해결하기 위해 이전의 데이터를 이용하는 경우 메모리 어딘가에 저장해 두었다가 다시 꺼내와서 계산하는 방식이다. 주로 배열을 이용한다. 이 방식을 이용하면 함수를 부르는 것에 비해 컴퓨터 자원을 적게 소모하게 된다.)

1일 경우를 생각해보면, 1밖에 없다. 즉 1가지가 있다.

2일 경우를 생각해보면, 1+1 과 2 밖에 없다. 즉 2가지 이다.

3일 경우를 생각해보면, 1+1+1, 1+2, 2+1, 3 이다. 즉 4가지 이다.

이런식으로 계속 수를 늘려보자. 

4일 경우에는 3인 경우에 +1을 뒤에 붙여서 4가지의 경우를 생각할 수가 있다. 또 2일 경우에 뒤에 +2를 붙여서 2가지 경우를 생각해낸다. 마지막으로 1인 경우 뒤에 +3을 붙여서 1가지의 경우를 생각할 수가 있다. 이러한 식으로 계속 지나가다 보면, n 의 방법의 가짓수는 [n-1의 가짓수 + n-2의 가짓수 + n-3의 가짓수] 라는 공식이 성립하게 된다. 이것을 이용해 간단한 코드를 짜 보았다.

#include <stdio.h>
 
int a[15];
 
int plus(int n)
{
    if(n==1) return 1;
    if(n==2) return 2;
    if(n==3) return 4;
    if(a[n]!=0)
    {
        return a[n];
    }
    return a[n]=plus(n-1)+plus(n-2)+plus(n-3);
}
 
int main()
{
    int num,j;
    scanf("%d",&num);
    for(int i=0;i<num;i++)
    {
        scanf("%d",&j);
        printf("%d\n",plus(j));
    }
}

내가 생각한 방법은 동적 계획법을 이용해 풀었으나, 일반적인 배열에 저장해 두는 식으로 만들어 풀어도 상관없을 것 같다. 하지만 함수를 이용해 깔끔하게 모듈화를 하면 보기에도 좋을 것 같다는 생각이 든다.