[백준 1904번: 01타일] java 풀이

백준 1904번 : 01타일 바로가기

동적계획법

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 쉽게 말하면 답을 재활용한다고 볼 수 있다. 하위 부분의 답을 기억해놓고 이를 바로 활용하여 문제를 푸는 방식이다.

동적계획법(DP)은 점화식을 구하는 것이 중요하다.

점화식을 구해서 재귀적인 방법(TOP-DOWN)으로 풀거나 반복문(BOTTOM-UP)을 이용하여 풀 수 있다.

F(n) = F(n-1) + F(n-2)

이번 문제의 점화식은 위와 같다.
n=1, 1
n=2, 2
n=3, 3
n=4, 5
n=5, 8

이와 같이 피보나치 수열처럼 증가하므로 점화식을 쉽게 세울 수 있다.

처음에 문제를 복잡하게 생각하느라 헤맸는데 생각보다 간단한 문제였다...

• 재귀함수를 이용한다
• (1 ≤ N ≤ 1,000,000) 이므로 답을 담는 배열의 크기를 1000001로 잡는다.
• 처음 인덱스 0, 1, 2에 답을 초기화해준다.
• 나머지 인덱스에는 -1로 초기화한다.
• F(n) = F(n-1) + F(n-2) 를 이용하여 재귀함수를 작성한다. 배열 값이 -1인 경우는 아직 계산되지 않았기 때문에 위의 점화식을 이용하여 재귀함수를 호출한다.
• 배열 값이 -1 이외의 값이면 이미 계산돼서 저장된 답이기 때문에 그대로 해당 배열 값을 리턴한다.

참고 블로그 : https://st-lab.tistory.com/125

🔑 java 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int arr[]=new int[1000001];
    static int cal(int N){
        if(arr[N]==-1)
            arr[N]=(cal(N-1)+cal(N-2))%15746;
        return arr[N];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr[0]=0;
        arr[1]=1;
        arr[2]=2;
        for(int i=3; i<arr.length; i++)
            arr[i]=-1;
        System.out.println(cal(N));
    }
}