๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
  • ์žฅ์›์ต ๊ธฐ์ˆ ๋ธ”๋กœ๊ทธ
๐Ÿ’ป Computer Science/- Data Structure, Algorithm

[์•Œ๊ณ ๋ฆฌ์ฆ˜ PS] ๋ฐฑ์ค€ 11726 2*n ํƒ€์ผ๋ง ์ž๋ฐ” ๋ฌธ์ œ ํ’€์ด

by Wonit 2021. 1. 26.

๋ฌธ์ œ

ํ•ด๋‹น ํฌ์ŠคํŒ…์€ ๋ฐฑ์ค€์˜ 11726๋ฒˆ 2*n ํƒ€์ผ๋ง ์˜ ์ ‘๊ทผ๊ณผ ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•์„ ์„ค๋ช…ํ•œ ๊ธ€ ์ž…๋‹ˆ๋‹ค.
์ •๋‹ต ์†Œ์Šค ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•˜์‹œ๋ ค๋ฉด solve url ์—์„œ ํ™•์ธ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ์–ด๋–ค ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ๋จผ์ € ์ƒ๊ฐํ•ด๋ณด์ž.

ํ•ด๊ฒฐ๋ฒ•

2 x n์˜ ์ง์‚ฌ๊ฐํ˜•์„ ์ฑ„์›Œ์•ผ ํ•˜๋Š”๋ฐ, ์šฐ๋ฆฌ์—๊ฒ 2๊ฐ€์ง€ ํƒ€์ผ์ด ์ฃผ์–ด์ง„๋‹ค.

  • 1 x 2
  • 2 x 1

์ด๋Ÿฐ ํƒ€์ผ์„ ๊ฐ€์ง€๊ณ  2 x n ํฌ๊ธฐ์˜ ํƒ€์ผ์„ ์ฑ„์›Œ์•ผ ํ•œ๋‹ค.

์ ‘๊ทผ๋ฒ•

 

ํฌ๊ธฐ๊ฐ€ 2 x n ์ธ ํƒ€์ผ์ด ์žˆ์„ ๋•Œ, ์ƒˆ๋กญ๊ฒŒ ํƒ€์ผ์ด ์ถ”๊ฐ€๋˜๊ธฐ ์œ„ํ•ด์„œ๋Š” 2๊ฐ€์ง€ ๋ฐฉ๋ฒ•๋งŒ ์กด์žฌํ•œ๋‹ค.

 

  1. 2 x (n-1) ๋ฒˆ์งธ ํƒ€์ผ์—์„œ 2 x 1 ํƒ€์ผ์ด ์ถ”๊ฐ€๋œ ๊ฒฝ์šฐ
  2. 2 x (n-2) ๋ฒˆ์จฐ ํƒ€์ผ์—์„œ 2 x 2 ํƒ€์ผ์ด ์ถ”๊ฐ€๋œ ๊ฒฝ์šฐ

๊ทธ๋Ÿผ ์ ํ™”์‹์„ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์„ธ์šธ ์ˆ˜ ์žˆ๋‹ค.

arr[n] = arr[n-1] + arr[n-2];

์ •๋‹ต ์ฝ”๋“œ

import java.io.*;

public class Main {

    static int[] memo = new int[1001];

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        bw.write(String.valueOf(dp(n));
    }
    private static int dp(int n){
        if(n == 1 || n == 0) return 1;
        if(memo[n] > 0) return memo[n];

        memo[n] = dp(n-1) + dp(n-2);
        memo[n] %= 10007;
        return memo[n];
    }
}

๋ฌธ์ œ ํšŒ๊ณ 

DP ๋ฌธ์ œ์˜ ํŠน์„ฑ์„ ํŒŒ์•…ํ•˜๊ธฐ ์œ„ํ•ด์„œ ์ง€๊ธˆ๊นŒ์ง€๋Š” ์†์œผ๋กœ ์ฒ˜์Œ ๋ถ€ํ„ฐ n ๊นŒ์ง€ ๊ฐ€๋ฉด์„œ ํŠน์„ฑ์„ ์ฐพ์„ ๋–„ ๊นŒ์ง€ ๋ฐ˜๋ณตํ•˜์˜€๋‹ค.

 

์ง€๊ธˆ๊นŒ์ง€ ๋ฌธ์ œ๋“ค์€ ์ด๋ ‡๊ฒŒ ์ž˜ ํ’€๋ ธ์ง€๋งŒ ์ด๋ฒˆ ๋ฌธ์ œ๋Š” ๊ทธ๋ ‡์ง€ ์•Š์•˜๋‹ค.


์ด๋ฒˆ ๋ฌธ์ œ๋Š” n์ผ ๋•Œ ์–ด๋–ค ํŠน์„ฑ์„ ๊ฐ–๊ณ  ์žˆ๋Š”์ง€๋ฅผ ํŒŒ์•…ํ•˜๋Š” ๊ฒƒ์ด ์ค‘์š”ํ–ˆ๋‹ค.


์ด๋ ‡๊ฒŒ ์Šคํ‚ฌ ํ•˜๋‚˜๊ฐ€ ๋Š˜์—ˆ์œผ๋‹ˆ ๋‹ค์Œ ๋ฌธ์ œ์—๋„ ์ ์šฉํ•ด๋ณด๋ ค ํ•œ๋‹ค.

์ •๋‹ต ์†Œ์Šค ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•˜์‹œ๋ ค๋ฉด solve url ์—์„œ ํ™•์ธ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

๋Œ“๊ธ€