백준 1904번 01타일(JAVA,DP)

<풀이방식>

처음에 일단 DP배열에 들어갈 경우의 수를 하나씩 적다보니 피보나치 수열 형태를 가진다고 생각했다. 친구에게 물어보니 00타일 1타일을 쓰는경우가 곧 2개 , 1개씩 가져가는 피보나치 수열과 동일한 형태임을 알려주었다.
비슷하게 타일이 가로1,세로2의 길이를 가지면서 이를 가로 세로로 놓는 프로그래머스에 2*N 이라는 문제도 비슷하게 풀이 가능할 것이다.

dp[i] = dp[i-1] + dp[i-2]; 라고 쉽게 풀었으나 for문 안쪽에서 미리 %15746 을 처리해줘야 int배열이 터지지 않았다. for문 나오고 결과값에 나눠서 틀렸다.

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


public class Main {
	public static void main(String[] args ) throws IOException{
		Scanner sc = new Scanner(System.in);

		int size = sc.nextInt();
		int [] dp = new int [size+1]; // 경우의 수 담는 배열
		
		if(size >=1)
			dp[1] = 1;
		if(size >=2) {
			dp[2] = 2;
			
			for(int i = 3 ; i <dp.length; i++) {
				dp[i] = (dp[i-1] + dp[i-2])%15746;
			}
		}
		
		System.out.println(dp[size]);
	}
}