/ BOJ

BOJ_1904_01타일_JAVA

문제 : 01타일

링크 : BOJ_1904_01타일

접근 방식

N이 1일때 1으로 1개

N이 2일때 00, 11 2개

N이3일때 001,100,111 3개

N이 4일때 0011,0000,1001,1100,1111 5개,

N이 5일때 11111, 11100, 11001, 10011, 00111, 10000, 00100, 00001 8개

N이 6이라면 111111, 111100, 111001, 110011, 100111, 001111, 110000, 100001, 100100, 000011, 000011, 001001, 000000 13개이다.

1, 2, 3, 5, 8, 13 … 어딘가 익숙할 것이다.

이것은 다른 문제의 탈을 쓴 피보나치 수열 문제이다. 시간제한이 0.75초로 매우 짧은 것은 DP를 사용하라는 의미이다.

풀이 방법

  1. 결과값을 저장할 배열을 N+1개만큼 선언한다. N+1개만큼 선언하는 이유는, 해당 문제의 시작이 피보나치수열의 2번째부터이기 때문이다.

  2. 피보나치 수열의 초기값을 dp배열의 0번, 1번에 할당한다.

  3. i는 2부터 N번까지 반복을 돌려서 피보나치 수열을 계산하여 저장한다.

  4. 주의해야할 점은 문제에서 원하는 값은 15746으로 나눈 나머지이고, 주어지는 값이 매우 커서 허용가능한 int값을 넘어선다. (a + b) % c = a % c + b % c의 성질을 이용해서 값을 더할때마다 15746으로 나머지 연산을 해주어야한다.

  5. N번째까지 반복을 돈 후, dp배열의 N-1번째 값을 출력한다.

소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class BOJ_1904_01타일 {


	public static void main(String[] args) throws NumberFormatException, IOException {

		// 버퍼드리더로 값 읽어오기
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(in.readLine());
		N = N + 1;
		int[] dp = new int[N];
		dp[0] = 1;
		dp[1] = 1;

		for(int i=2;i<N;i++) {
			dp[i] = (dp[i-1] + dp[i-2])%15746;

		}

		System.out.println(dp[N-1]);
	}

}

//
//	static long fiboDp(int N) {
//		
//		if(N == 0) {
//			return 0;
//		}
//		if(N == 1) {
//			return 1;
//		}

//		if(dp[N] != 0) {
//			return dp[N];
//		}
//		dp[N] = fiboDp(N-1) + fiboDp(N-2);
//		return dp[N];
//		

//	}