백준 9095 - 1,2,3 더하기

 

정수 N을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제이다.

 

-먼저 상태와 가장 작은문제를 종료하기 위한 조건을 생각해보자: 상태: N ,종료조건: ?

(종료조건 ->더 이상 재귀호출하지않고 이전 호출로 return 시작)

 

점화식을 만들면서 종료조건을 생각해보자.

 

문제를 해결하면서 변하지 않는 값 -> 각 수를 만드는 경우의 수 

가령 1 => 1개, 2 = 1+1, 2 두개 , 3 = 1+1+1, 1+2, 2+1, 3 4개 등등의 경우의 수는 다른 N을 구하는 과정에서 나오더라도 변하지 않을 것이다. 

 

 

점화식 

N이라는 숫자를 만들기 위해 1,2,3만을 이용해야한다면,

N = N-1 +1

   = N-2 +2

   = N-3 +3 꼴 일 것이다.

예제의 4를 보면 

4 = 1+3, 2+2 등으로 표현할 수 있는데 이는 또 각각의 1,2로 쪼개질 수 있다. 따라서 

아래와 같이 잘개 쪼개질 수 있는데, 각 쪼개진 방법들은 3을 만드는데 혹은 2를 만드는데 쓰이는 경우의 수이다.

1+(1+1+1) ->D[3]의 경우의 수 중 하나

1+(1+2) ->D[3]의 경우의 수 중 하나 

2+(2) D[2]의 경우의 수 중 하나

---이런 느낌일 것이고 이를 확장해서 생각해보면

 

N = 8이라면 

7 +1 혹은 6+2 혹은 5+3의 꼴일 것이고 각 7과 6과 5는 다시 1,2,3의 더하기로 쪼개질 수 있으므로, 각 7과 6과 5가 만들어지는 경우의 수가 8에 포함된다고 볼 수 있다.

 

따라서 점화식은 

D[N] = D[N-3] + D[N-2} + D[N-1] 이다.

 

종료조건은 n==1,n==2,n==3일때 구하기도 쉽고, 가장 바탕이되는 단계이므로 각각 1개 2개 4개를 return해주도록하자.

n은 양의 정수라고 했으니 n이 0과 같거나 작아질때는 0개를 return하도록 해두자.

 

public class Solution {
    public static int[] d;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());

      while(t -- > 0){
          int n = Integer.parseInt(br.readLine());
          d = new int[n+1];
          d[1] = 1;
          d[2] = 2;
          d[3] = 4;
          for(int i=4; i<=n;i++){
              d[i] = d[i-1]+d[i-2]+d[i-3];
          }
          System.out.println(d[n]); //빠업
          System.out.print(OTT(n)); //탑따


      }

    }
    public static int OTT(int n){
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(n == 3) return 4;
        if(n <= 0) return 0;

        d[n] = OTT(n-3) + OTT(n-2) + OTT(n-1);

        return d[n];
    }

}