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

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

 

---

• 문제설명
  먼저 첫 번째 줄에 테스트 케이스의 개수를 입력받고 이 테스트 케이스만큼 정수를 입력받는다. 그리고 이 정수에 대해서 1, 2, 3의 합으로 나타내는 방법의 수를 출력하면 된다.

• 제출코드     

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String [] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int [] dp = new int[12];

        for(int i = 0; i < T; i++){
            int n = Integer.parseInt(br.readLine());

            dp[0] = 0;
            dp[1] = 1; //1
            dp[2] = 2; //1+1, 2
            dp[3] = 4; // 1+1+1, 1+2, 2+1, 3

            for(int j = 4; j <= n; j++){
                dp[j] = dp[j-1] + dp[j-2] + dp[j-3];
            }
            System.out.println(dp[n]);
        }
    }
}

 

• 코드설명
  dp배열을 하나 만들어 어떠한 정수에 해당하는 1,2,3의 합으로 나타내는 방법의 수를 그 index에 기록해 나가는 방법이다.
  먼저 0,1,2,3 의 방법의 수를 각각의 index에 저장해 준다. 이 부분이 초기 설정하는 부분이다. 그 후에는 for문을 돌려서 기록해 둔 정보를 사용해서 원하는 값을 알아내면 된다.

---

• 마무리
  먼저 이 문제를 풀기 위해서는 다이나믹 프로그래밍의 개념을 알아야 한다.

다이내믹 프로그래밍이란?
여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아 올려 주어진 문제를 해결하는 알고리즘

DP를 푸는 과정?
1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 설정하기

DP를 풀기 위해서는 먼저 테이블을 정의해야 하고 점화식을 찾은 후에 초기 값을 정해야 한다.
일단 점화식만 찾고 나면 그 뒤는 초기 값을 채워넣은 후에 반복문을 돌면서 배열을 채우면 끝이어서 구현이 굉장히 쉽다.
하지만 지금 단계에서는 DP문제를 푸는데에 있어서 연습하는 단계라서 다양한 관련 문제를 많이 풀면서 감을 찾는 게 우선이라고 생각한다.