[BaekJoon] 1904 01타일 (java)

🔗 문제 링크

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

📝 문제 풀이 방법

해당 문제는 N이 증가함에 따라 생성되는 결과에 대한 점화식을 도출하여 풀어야하는 문제이다.

문제의 규칙은 다음과 같다. N번째 생성되는 수열은 N-1개로 생성되는 수열에 1을 붙인 경우의 수와 N-2개로 생성한 수열에 00타일을 붙이는 경우의 수가 된다.
즉, $arr[N] = arr[N-1]+ arr[N-2]$가 되는 것이다.

이를 이용해 피보나치 문제와 같이 Dynamic Programming으로 코드를 작성해보았다.

👨🏻‍💻 작성한 코드

import java.io.*;
public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int[] arr = new int[n+1];
		
		arr[1] = 1;
		if (n >= 2) arr[2] = 2;
		
		if (n >= 3) {
			for (int i=3; i<=n; i++) {
				arr[i] = (arr[i-1] + arr[i-2]) % 15746;
			}
		}
		
		System.out.println(arr[n]);
	}

}