[백준 / 9095] 1, 2, 3 더하기 - JAVA

[백준 / 9095] 1, 2, 3 더하기 - JAVA

Dynamic Programming으로 푸는 문제입니다.

규칙을 찾아 초기값과 점화식만 잘 생각한다면 의외로 쉽게 풀리는 문제입니다.

물론 그 과정이 험난할 수도 있습니...다.

import java.util.Scanner; public class Main { static int[] dp = new int[11]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); dp[1] = 1; dp[2] = 2; dp[3] = 4; for (int i=4;i<11;i++){ dp[i] = dp[i-1]+dp[i-2]+dp[i-3]; } for (int i=0;i

우선, 저의 코드입니다.

dp[1], dp[2], dp[3] 은 초기값입니다. 이는 어느정도 사람 머리로 생각할 수 있는 선에서 규칙을 찾아보는 과정입니다.

1은 1하나, 2는 1+1과 2 두 개, 3은 1+1+1, 1+2, 2+1, 3 해서 네 개 이런식으로 초기값을 가져갑니다.

하고 dp[4]까지 구해본다면 7이 나옵니다.

그렇다면 규칙, 즉 점화식은 전에 세개를 더하면 그 다음 것.

DP 문제를 풀 때는 초기값과 점화식을 세우는 것이 중요합니다.

그럼 다들 화이팅..!

from http://soobinhand.tistory.com/17 by ccl(A) rewrite - 2021-10-21 05:27:55