https://www.acmicpc.net/problem/1904
문제
> 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다.
> 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.
> 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다.
> 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.
> 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다.
> 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다.
(01, 10은 만들 수 없게 되었다.)
> 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.
> 우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다.
> 단 타일들은 무한히 많은 것으로 가정하자.접근
DP를 사용하여 문제를 푼다. 2xn타일 문제와 비슷한 문제이다.
00짜리 한덩이와 1짜리 한덩이로 만드는것이다. 문자 앞에 0이 오면 안된다 라는 조건이 없기 때문에 가능하다.
1xn짜리 타일을 1x1과 1x2짜리 타일로 채운다고 생각하면 된다.
그래서 1부터 쭉 써보면
1 -> 1개, 2 -> 2개, 3 -> 3개, 4 -> 5개, 5 -> 8개, 6 -> 13개가 된다. 이는 i번째는 i-2와 i-1번쨰를 더한 값이다.
문제해결
> N을 입력받고 1부터 N까지를 구해야하므로 dp배열의 크기를 N+1로 만들어준다.
> 초기값으로 1자리가 1뿐이므로 1을 주고, 0자리는 쓰지 않지만 2자리를 위해 1로 준다.
> 2부터 N까지 반복문으로 앞서 구한 공식을 사용한다.
> i번째에 대해 i-2번째와 i-1번째의 값을 더해 구해준다.
> 문제에서 15746을 나눈 값이라는 조건이 있으므로 각 i값에 나머지연산을 해준다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//1904번 01타일
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] dp = new int[N+1];
dp[0] = dp[1] = 1;
for(int i = 2; i <= N; i++) dp[i] = (dp[i-2] + dp[i-1]) % 15746;
System.out.print(dp[N]);
}
}
후기
앞에 00이 와도 되므로 쉬웠다.
