코딩테스트

[백준-9095번] 1, 2, 3 더하기 풀이 - Java

UnaUna 2025. 6. 3. 02:23
반응형

🚀 문제

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

 

 

🚀 접근 방법

DP 문제이다.

보면 이전 3개의 합과 같은 것을 볼 수 있다.

 

점화식

dp[i-1]+dp[i-2]+dp[i-3]

1 2 3 4 5
1 1+1
2
1+1+1
1+2
2+1
3
1+1+1+1
1+1+2
1+2+1
1+3
2+1+1
2+2
3+1
1+1+1+1+1
1+1+1+2
1+1+2+1
1+2+1+1
1+2+2
1+1+3
1+3+1
2+1+1+1
2+1+2
2+2+1
2+3
3+1+1
3+2
1개 2개 4개 7개 13개

 

 

🚀 코드

import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

            int[] dp = new int[m+1];
            dp[1] = 1;
            if(m>=2)
                dp[2] = 2;
            if(m>=3)
                dp[3] = 4;

            for(int j=4; j<=m; j++){
                dp[j] = dp[j-1]+dp[j-2]+dp[j-3];
            }

            bw.write(dp[m]+"\n");
        }

        bw.flush();
        br.close();
        bw.close();
    }
}
반응형