๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

[DP] 1. ๊ณ„๋‹จ์˜ค๋ฅด๊ธฐ

์‹œํ๋ฆฌํ‹ฐ์ง€ํ˜ธ 2024. 3. 2.

<<ํ’€์ด>>

 

dp: ์•ž์— ๊ตฌํ•œ ๊ฐ’์„ ๋ฉ”๋ชจ์ œ์ด์…˜์œผ๋กœ ์ €์žฅํ•ด๋‘๊ณ  ์ด๋ฅผ ์ด์šฉํ•ด์š” ๋‹ค์Œ ๋‹จ๊ณ„์—์„œ ์ด์šฉํ•˜๋Š” ๋ฐฉ์‹์ด๋‹ค.

๊ทธ ์ค‘์—์„œ๋„ ๋ฐ‘์—์„œ ์˜ฌ๋ผ๊ฐ€๋Š” ๋ฐฉ์‹์„ bottom-up ๋ฐฉ๋ฒ•์ด๋‹ค.

 

๋‚ด๊ฐ€ DFS ๋ฐฉ์‹๊ณผ ํ—ท๊ฐˆ๋ ธ์—ˆ๋Š”๋ฐ, ์ด ๋ฌธ์ œ๋ฅผ ๋ณด๊ณ  ์™€๋‹ฟ๋Š”๋‹ค. DFS๋Š” ์•„์˜ˆ ์žฌ๊ท€ํ•จ์ˆ˜๋กœ ์™„์ „ ๊นŠ์ด ์•„๋ž˜๊นŒ์ง€ ๊ฐ”๋‹ค๊ฐ€ ์˜ค๋Š” ๊ฑฐ๋ผ๋ฉด dp ๊ฐ™์€ ๊ฒฝ์šฐ๋Š” ์ด๋ฏธ ์ด์ „์˜ ๊ฐ’์„ ์ €์žฅํ•ด๋‘๊ณ  ๋ฐ”๋กœ ํ™œ์šฉํ•˜๋Š” ์ฐจ์ด์ ์ด ์žˆ๋‹ค. ๊ทธ๋ž˜์„œ dfs๊ฐ€ ๋ฉ”๋ชจ์ œ์ด์…˜์„ ํ™œ์šฉํ•˜๋”๋ผ๋„ dp๋ณด๋‹ค๋Š” ์‹œ๊ฐ„์ด ๋งŽ์ด ๊ฑธ๋ฆฌ๋Š” ๊ฒƒ์ด๋‹ค. 

import java.util.Scanner;

class Main {
    static int[] dy;
    public int solution(int n) {
        dy[1] = 1;
        dy[2] = 2;
        for (int i = 3; i <= n; i++) {
            dy[i] = dy[i - 2] + dy[i - 1];
        }
        return dy[n];
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        dy = new int[n + 1];
        System.out.println(T.solution(n));
    }
}

 

 

์•„์ง dp์— ๋Œ€ํ•ด ์ •ํ™•ํ•˜๊ฒŒ ์•ˆ๋‹ค๊ณ ๋Š” ํ•  ์ˆ˜ ์—†๋‹ค๊ณ  ์ƒ๊ฐํ•œ๋‹ค. ๋ฌธ์ œ๋ฅผ ์—ฌ๋Ÿฌ๊ฐœ ๋” ํ’€์–ด๋ณด๋ฉด์„œ ๋‚ด ๊ฒƒ์œผ๋กœ ๋งŒ๋“ค์ž !!

๋Œ“๊ธ€