[DP] 1. ๊ณ๋จ์ค๋ฅด๊ธฐ
<<ํ์ด>>
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์ ๋ํด ์ ํํ๊ฒ ์๋ค๊ณ ๋ ํ ์ ์๋ค๊ณ ์๊ฐํ๋ค. ๋ฌธ์ ๋ฅผ ์ฌ๋ฌ๊ฐ ๋ ํ์ด๋ณด๋ฉด์ ๋ด ๊ฒ์ผ๋ก ๋ง๋ค์ !!
'์ฝ๋ฉํ ์คํธ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค/1004/์ค๋ฒ3] ์ด๋ฆฐ ์์ (5) | 2024.03.12 |
---|---|
[๋ฐฑ์ค/2941/์ค๋ฒ5] ํฌ๋ก์ํฐ์ ์ํ๋ฒณ (7) | 2024.03.05 |
[๋ฐฑ์ค/1003/์ค๋ฒ3] ํผ๋ณด๋์น ํจ์ (6) | 2024.03.01 |
[DFS] 7. ์กฐํฉ์ ๊ฒฝ์ฐ์(๋ฉ๋ชจ์ด์ ์ด์ ) (6) | 2024.02.26 |
[๋ฐฑ์ค/1002/์ค๋ฒ3] ํฐ๋ (3) | 2024.02.25 |
๋๊ธ