[JAVA] 백준 11727번

11727번 - 2×n 타일링 2

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	static int[] dp;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());

		dp = new int[N + 1];

		dp[0] = dp[1] = 1;

		for (int i = 2; i <= N; i++) {
			if (i % 2 == 0) {
				dp[i] = dp[i - 1] * 2 + 1;
			} else {
				dp[i] = dp[i - 1] * 2 - 1;
			}

			if (dp[i] >= 10007) {
				dp[i] = dp[i] % 10007;
			}

		}

		bw.write(String.valueOf(dp[N]));

		bw.flush();
		bw.close();

	}

}

 

정답을 맞춘 풀이방법

1 . 이전 2*n 11727번 타일링 문제와 유사하며 DP를 활용한 Bottom - Up 방식으로 해결함

2.  n = 5 까지 직접 구해보면 n = 1 , 2 , 3, 4, 5일때 각각 1, 3, 5, 11, 21 값을 가짐

3.  이를 통해 n = 홀수 일때  dp[n-1] * 2 + 1, n = 짝수 일때  dp[n-1] * 2 - 1의 규칙을 가짐을 알 수 있음

4. 10007로 나누어 주지않으면 자료형의 범위가 초과되어 다른 값이 나오므로 유의해야함