문제풀이/DP

[PS] BOJ15989 1,2,3 더하기4 ( dp ) with JAVA

IT록흐 2023. 10. 18. 09:21
반응형

 

 

15989번: 1, 2, 3 더하기 4

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2

www.acmicpc.net

 

 

◎ 문제풀이

 

문제를 보고 DP를 떠올렸으나 '순서만 다른 것은 같은 것으로 본다'는 조건이 어려웠다. 순서만 다른 정렬을 같게 만들려면 오름차순으로 정렬하면 된다.

 

+1 로 끝난 식 뒤에는 +1만 올 수 있고

+2로 끝난 식 뒤에는  +1, +2만 올 수 있고

+3으로 끝난 식 뒤에는 +1, +2, +3만 올 수 있다. 

 

예를 들어 

 

dp[4][1] :  4를 만드는데 끝이 1인 경우의 수이다. 

dp[4][2] : 4를 만드는데 끝이 2인 경우의 수이다.

dp[4][3] : 4를 만드는데 끝이 3인 경우의 수이다.

 

dp[4][1] = dp[3][1] = 1

dp[4][2] = dp[2][1] + dp[2][2] = 1 + 1 = 2

dp[4][3] = dp[1][1] + dp[1][2] + dp[1][3] = 1 + 0 + 0 = 1

 

dp[4][1] + dp[4][2] + dp[4][3] = 1 + 2 + 1 = 4

 

정답은 4이다.

 

이를 코드로 구현해보자. 

 

◎ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//BOJ15989 1,2,3 더하기4
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());

        while(t-- > 0){
            int n = Integer.parseInt(br.readLine());
            int[][] dp = new int[n+1][4];

            for(int i=1;i<=n;i++){
                if(i==1) dp[1][1] = 1;
                if(i==2) dp[2][2] = 1;
                if(i==3) dp[3][3] = 1;

                if(i>1) dp[i][1] = dp[i-1][1];
                if(i>2) dp[i][2] = dp[i-2][1] + dp[i-2][2];
                if(i>3) dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3];
            }

            System.out.println(dp[n][1] + dp[n][2] + dp[n][3]);


        }
    }
}

 

반응형