1904_01 타일

사용 알고리즘: dp

사용 언어: java

 

package week31_32;

import java.util.*;

public class Main_bj_1904_01타일 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		// 1, 00
//		1-> 1 (1)
//		2-> 11 00 (2)
//		3-> 111 001 100 (3)
//		4-> 0011, 0000, 1001, 1100, 1111 (5)
//		1로 끝날 때, 뒤에 1만 붙이면 됨 = dp1[i] = dp1[i-1]+dp0[i-1];
//		0로 끝날 땐, dp0[i] = dp1[i-2]+dp0[i-2];
		int[] dp0 = new int[n + 1];
		int[] dp1 = new int[n + 1];
		dp1[1] = 1;
		if (n == 0)
			System.out.println(0);
		else if (n == 1)
			System.out.println(1);
		else {
			dp1[2] = 1;
			dp0[2] = 1;

			for (int i = 3; i < n + 1; i++) {
				dp1[i] = (dp1[i - 1] + dp0[i - 1]) % 15746;
				dp0[i] = (dp1[i - 2] + dp0[i - 2]) % 15746;
			}

//		System.out.println(Arrays.toString(dp0));
//		System.out.println(Arrays.toString(dp1));

			System.out.println((dp1[n] + dp0[n]) % 15746);
		}
	}

}

 

캬;

앞에 어떤 수가 왔든, 뒤에는 00과 1밖에 못 붙인다.

1은 길이가 하나이기 때문에, 바로 이전 길이 수에다가 1만 붙이면 된다.

0은 길이가 둘이기 때문에, 바로 이전이 아니라 -2 길이 수에다가 00을 붙이면 된다.

 

주의) 엣지 케이스 테스트 조심