백준 1904 01타일 자바

https://www.acmicpc.net/problem/1904

1904번: 01타일

연구실 프로젝트마감이 있어서 알고리즘 문제풀이에 투자할 시간이 없어서 오랜만에 게시글을 올린다. 

전형적인 동적계획법 문제였는데 동적계획법 문제를 안푼지 오래되서 그런게 기억이 잘나지않았다. 백트래킹으로 문제를 풀었는데 메모리 초과 오류가 발생했다.

 

배운점

동적계획법은 무조건 전의 결과값이 현재의 결과값에 영향을 미친다 즉 1~n 까지 경우를 손으로 직접해보면서 규칙을 찾는 것도 도움이된다. 이 문제의 경우 알고나면 피보나치 수열과 크게 다를 바가 없는 문제이다.

0의 경우는 입력조건이 자연수라 처리하지 않아도 문제가 발생하지 않았지만 1이 입력되는 경우 dp[2]가 생성되지 않기 때문에 조건문을 추가하였다.

 

 

풀이

package 동적계획법;
 
import java.io.*;
public class P01타일 {
    //점화식 한칸씩전진할떄 어떤값이 나오는지 알고 규칙을 찾아야함
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] dp  = new long[n+1];
 
        dp[1] = 1;
        if(n>1)
        dp[2] = 2;
        for(int i=3;i<=n;i++){
            dp[i] = dp[i-2]+dp[i-1];
            dp[i]%=15746;
        }
        System.out.println(dp[n]);
    }
 
}