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

문제 1,2,3 더하기

일단 DP문제라서 DP로 푸려고 노력을 하였다.

그렇지만 아직 나에겐 역부족이었다 ㅠㅠㅠ 

그래서 다른 블로그를 참고해서 답안을 생각했다. 

일단 간단하게 이야기 하자면 

1,2,3으로 이루어진 숫자 N의 경우의 수를 보면 

f(N) = f(N-3) +f(N-2)+f(N-1)

을 하면 구할 수 있다. 

( ※f(N) = 숫자 N의 경우의 수이다. )

예를 들면 숫자 N=4 라고 한다면 

f(4) = f(1)+f(2)+f(3)

즉 1,2,3의 경우의 수를 더하면 숫자 4의 경우의 수를 구할 수 있다. 

만약 숫자 1,2로만 이루어져 있다면

점화식은 

f(N) = f(N-2)+f(N-1) 

이렇게 될 것이다. 하지만 문제는 1,2,3으로 이루어져있어서  

f(N) = f(N-3) +f(N-2)+f(N-1)

점화식이 이렇게 되는 것이다. 

그래서 일단 밑에 각각 숫자 1,2,3의 경우의 수를 써보았다. 

이렇게 될 것이다. 

밑에 그림을 보면 

숫자 4(N)를 만들려면 

1) (N-3)+3

2) (N-2)+2

3) (N-1)+1

세 가지 경우의 수가 있다. 

1)번을 예를 들자면 

N-3 = 4 - 3 = 1

1의 경우의 수에서 +3을 해주면 된다.

즉 1의 경우의 수는 

1

여기다가 +3을 해주어야 함으로 1+3이 된다. 

그럼 1+3 은 4의 경우의 수중에 하나가 된다. 

이런 식으로 2번, 3번도 한다면 숫자 4의 경우의 수들이 구할 수 있다.

따라서 숫자 4의 경우의 수는 

1+2+4 = 7 이 된다. 밑의 그림을 참고하길 바랍니다.

import java.io.*;
 
 
public class Main {
 
    BufferedReader br;
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int[] numbersOfCase = new int[12];//경우의 수 배열
 
    void Solve() throws IOException {
        //br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        StringBuffer sb = new StringBuffer();
        numbersOfCase[0] = 0;
        numbersOfCase[1] = 1;//숫자 1 경우의 수
        numbersOfCase[2] = 2;//숫자 2 경우의 수
        numbersOfCase[3] = 4;//숫자 3 경우의 수
        for (int i = 4; i <= numbersOfCase.length - 1; i++) {
            numbersOfCase[i] 
                    = numbersOfCase[i - 1] + numbersOfCase[i - 2] + numbersOfCase[i - 3];
        }
 
        while (N-- > 0) {
            int num = Integer.parseInt(br.readLine().trim());
            sb.append(numbersOfCase[num] + "\n");
        }
        br.close();
        System.out.println(sb);
    }
 
 
    public static void main(String[] args) throws IOException {
        new Main().Solve();
    }
}

내 글을 보고 다른 누군가는 쉽게 이해가 되었으면 한다!