Algorithm/Baekjoon

[Algorithm/Baekjoon] 1, 2, 3 ๋”ํ•˜๊ธฐ 4 - 15989 (S1/JAVA)

dpdms2148 2023. 7. 19. 22:47
728x90

๐Ÿ“‘๋ฌธ์ œ๋งํฌ

 

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

๐Ÿ’ป์ฝ”๋“œ

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] dp = new int[100001][3];
        dp[1][0] = dp[2][0] = dp[2][1] = dp[3][0] = dp[3][1] = dp[3][2] = 1;

        for (int i = 4; i < 100001; i++) {
            dp[i][0] = dp[i-1][0];                          // ...+1๋กœ ๋๋‚˜๋Š” ๊ฒฝ์šฐ
            dp[i][1] = dp[i-2][0] + dp[i-2][1];             // ...+2๋กœ ๋๋‚˜๋Š” ๊ฒฝ์šฐ
            dp[i][2] = dp[i-3][0] + dp[i-3][1] + dp[i-3][2];// ...+3๋กœ ๋๋‚˜๋Š” ๊ฒฝ์šฐ
        }

        int t = Integer.parseInt(br.readLine());
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n][0]+dp[n][1]+dp[n][2]).append("\\n");
        }
        System.out.print(sb);
    }
}

โณํšŒ๊ณ 

  • ์ค‘๋ณต์„ ์ œ๊ฑฐํ•˜๊ธฐ ์œ„ํ•ด์„œ ์ˆซ์ž๊ฐ€ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ๊ตฌ์„ฑ๋˜๋„๋ก ํ•˜์˜€๊ณ , ๊ฒฝ์šฐ๋ฅผ 3๊ฐ€์ง€๋กœ ๋‚˜๋ˆ„์—ˆ๋‹ค.
728x90