백준 1904번 : 01타일

 문제

www.acmicpc.net/problem/1904

1904번: 01타일

1904 01타일

 

 구현 방법

 dp로 구현하였습니다. N을 구했을 때 N이 1일 때 1, 2일 때 2, 3일 때 3, 4일 때 5, 5일 때 8 .. 이므로 dp[n] = dp[n-2]+dp[n-1]이 점화식임을 알 수 있습니다.

주의할 점은 출력이 N의 개수가 아니라 15746을 나눈 나머지를 출력해야하므로 dp를 저장할 때 아예 나눠주었습니다.

 

 구현 코드

package BOJ.Silver;

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

public class BOJ1904_01타일 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] dp = new int[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])%15746;
		}
		
		System.out.println(dp[N]);
	}
}

 

정답!