[백준] 15989: 1, 2, 3 더하기 4 - JAVA

05 Oct 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

1만 써서 나타내는 방법은 1가지씩 가지고 있으므로 dp배열을 1로 초기화한다.

2가 추가되기 위해서는 i-2를 나타내는 방법들의 뒤에 2를 붙이면된다.

반복문을 통헤 dp[i] += dp[i - 2]를 적용해준다.

마찬가지로 3을 추가하려면 i-3을 나타내는 방법에 3을 붙이면 된다.

dp[i] += dp[i - 3]을 적용한다.

---

메모리: 14304KB

시간: 132ms

언어: Java 11

코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        int[] arr = new int[T];
        int max = 0;
        for (int i = 0; i < T; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }

        int[] dp = new int[max + 1];
        Arrays.fill(dp, 1);

        for (int i = 2; i < max + 1; i++) {
            dp[i] += dp[i - 2];
        }

        for (int i = 3; i < max + 1; i++) {
            dp[i] += dp[i - 3];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            sb.append(dp[arr[i]]).append("\n");
        }

        System.out.println(sb);
    }

}