백준 2748 자바

DP를 공부하고 남기는 글입니다. 완전히 공부한 건 아니라서 설명이 미흡할 수 있습니다.

구글에 쳐보시면 더 지식이 많으신 분들이 많으니 자세한 건 그 분들 설명을 참고해주시길 바랍니다.

 

우선 dp의 기본적인 문제입니다.

제가 dp를 공부할 때 가장 중요하다고 생각한 부분은 점화식, 메모이제이션입니다. 아마 이 두 단어는 다른 분들의 설명에서도 많이 나올 것이라고 생각합니다.

 

피보나치 수가 대표적인 점화식 F(n) = F(n-1) + F(n-2)를 가지고 있으니 가장 기본적인 문제가 아닐까 싶습니다.

 

import java.io.*;
import java.util.*;
public class Main {

    static Long[] dp;

    public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());

    dp = new Long[N+1];

    dp[0] = 0L;
    dp[1] = 1L;
    dp[2] = 2L;

    System.out.println(sol(N));

    }
    static long sol(int N) {

        if(dp[N] == null) {
            dp[N] = sol(N-1) + sol(N-2);
        }
        return dp[N];
    }
}

 

Top Down (재귀)로 푼 방법이고 범위 때문에 long으로 풀었습니다.

 

int[], long[] 배열은 선언만 했을 때 기본값이 0

Integer[], Long[] 배열은 선언만 했을 때 기본값이 null이기 때문에 아래 함수 부분에 

if(dp[N] == null) {
    dp[N] = sol(N-1) + sol(N-2);
}
return dp[N];

라고 작성했습니다.

어려워도 계속 하다 보면 조금씩 감이 올 겁니다 ㅜ