[백준] 9095번 - 1,2,3 더하기 (Java)

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

<문제 분석>

메모이제이션을 좀 안다고 생각했는데 한 방 먹은 문제다. 1시간 동안 고민했는데 풀지 못했다.

알고 봤더니 1~3까지 숫자를 계산할 때 약간의 상상력을 보태야 하는데 그까지 생각이 미치지가 못했다.

 

* DP(Dynamic Programming) 문제 푸는 공식 3단계

1) DP 테이블 정의

2) 점화식 찾기

3) 초기값 정하기

 

1) DP 테이블 정의

  - DP테이블은 1,2,3의 합으로 조합할 수 있는 경우의 수를 가진다.

  - 정수 n은 < 11이므로 DP[10+1]로 구성해서 값을 미리 구한 다음에 TC는 이미 계산해놓은 DP테이블의 값을 출력하도록 구현한다.

  ex) 1, 2, 3의 경우의 수를 구해보자.

  - DP[1] = 1

  - DP[2] = 1 + 1

                 2

  - DP[3] = 1 + 1 + 1

                 1 + 2

                 2 + 1

                 3

  - DP[4]의 값들과 비교를 해보면 아래와 같다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

잘 살펴보면DP[4]의 경우의 수들은  DP[1]의 값들에 +3을 한 것과 같고, DP[2]의 값들에 +2를, DP[3]의 값들에 +1을 한 것과 같은 것을 볼 수 있다.

 

2) 점화식 찾기

DP[4] = DP[3] + DP[2] + DP[1]이다.

즉, DP[K] = DP[K-1] + DP[K-2] + DP[K-3]이다.

 

3) 초기값 정하기

DP[1] = 1

DP[2] = 2

DP[3] = 4

 

 

<코드 구현>

import java.util.Scanner;
import java.lang.Math;

//[백준] 9095번 - 1,2,3 더하기 (Java)

public class Main {
	static int T;//입력 데이터의 개수
    static int Data[];
    static int DP[] = new int[10+1];

	public void InputData()
	{
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
        Data = new int[T];
		for (int i = 0; i < T; i++) 
		{
			Data[i] = sc.nextInt();
		}
		sc.close();
	}
	
	public void Solve() {
        // 1.DP 테이블 초기화 및 값 종류 정하기
        // 피보나치 수열의 0과 1 횟수 저장
        for (int i=0; i<=10; i++) {
            DP[i] = -1;
        }
        // 2. 초기값 설정
        DP[0] = 0; // 0
        DP[1] = 1; // 1
        DP[2] = 2; // 1+1, 2
        DP[3] = 4; // 1+1+1, 1+2, 2+1, 3

        // 3. 정화식 구현
        for (int i=4; i<=10; i++) {
            DP[i] = DP[i-1] + DP[i-2] + DP[i-3];
        }
	}
    
	public static void main(String[] args) 
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();

		//출력
		for (int i = 0; i < T; i++) 
		{
            System.out.println(DP[Data[i]]);
		}
	}
}

 

<결과 제출>