[백준] JAVA 자바 : 1, 2, 3 더하기 (9095번)

---

사실 아직까지 DP 알고리즘 문제들은 대개 비슷한 유형이라서…
그냥 dp[] 배열에 이전 값들의 경우의 수를 저장해둔 다음 바텀탑이나 탑다운 방식으로 dp[] 배열을 완성해 나가면 된다. 나 같은 경우는 바텀탑이 편해서 바텀탑만 사용하는 중…

이 문제 같은 경우도 똑같이 해결할 수 있다!
그러나 최대 3까지 더할 수 있으므로 나는 초깃값을 3개 설정해 두고, for 반복문을 4부터 n까지 돌리게 작성했다.

 

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

public class Sum123 {

    public static int stoi(String str) {
        return Integer.parseInt(str);
    }

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

        int[] dp = new int[11];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        int T = stoi(br.readLine()); // 테스트의 개수

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

            for (int j=4; j<=n; j++) {
                dp[j] = dp[j-1] + dp[j-2] + dp[j-3]; // 각각 +1, +2, +3 해서 만드는 경우
            }

            System.out.println(dp[n]);
        }
    }
}

 

로그인

 

 

작성일자: 2023-11-24