[백준 1904번] 01 타일 (C++, Python)
https://www.acmicpc.net/problem/1904
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
이번 포스트에서는 백준 알고리즘 문제인 01타일을 포스트하겠습니다.
해당 문제는 solved.ac 기준으로 실버 3에 위치한 문제입니다.
먼저 문제입니다.
문제에서 완성된 타일의 길이 N이 주어졌을 때, 00 타일과 1 타일로 N 길이의 타일을 만드는 모든 경우의 수를 출력하는 문제입니다.
해당 문제는 이전 문제인 1로 만들기 문제와 비슷하게 바텀업 방식의 DP 알고리즘으로 해결할 수 있습니다.
먼저 N이 1인 경우와, 2인 경우는 각각 1와 2로 답을 알고 있으므로, 이 값들을 이용하여 경우의수를 구하면서 올라갑니다.
N이 3인 경우 111, 001, 100 으로 3가지가 나오는데, 이는 N이 1인 경우의 수와 N이 2인 경우의 수를 합친 값이 됩니다.
N이 4인 경우에도 0000, 1111, 1001, 1100, 0011 로 5가지가 나오는데, 이 또한 N이 2인 경우와 N이 3인 경우를 합친 값이 됩니다.
이유로는 N칸의 타일을 만들기 위해서는 N-1 칸의 타일에 길이가 1인 타일만 붙여주면 N칸이 되고, N-2 칸의 타일에는 길이가 2인 타일만 붙여주면 N칸이 됩니다. 이때 N-1 칸의 타일에 길이가 1인 타일을 붙이면 끝은 1이되고, N-2 칸의 타일에 길이가 2인 타일을 붙이면 끝이 0이 됩니다. 그러므로 N-2 칸의 타일의 끝이 0인 경우는 마지막에서 두번째도 0이어야합니다. 즉 N-2 칸에서 마지막이 1인 경우는 N-1 칸의 타일에서 끝이 1로 되는 경우의 수와 중복되므로 제외됩니다.
그러므로 점화식은 dp[N] = dp[N - 1] + dp[N - 2] 로 정의할 수 있습니다.
N이 커지게 됐을 때, 결과값에서 오버플로우가 발생할 수 있으므로, 문제에서 15746으로 나눈 나머지를 출력하라고 요구합니다. 따라서 최종적으로 dp[N] = (dp[N - 1] + dp[N - 2]) % 15746 이 되겠습니다.
아래는 C++ 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <iostream>
using namespace std;
int dp[1000001] = {0,);
int main() {
int n;
cin >> n;
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
}
cout << dp[n];
return 0;
}
|
cs |
다음은 Python 코드입니다.
|
1
2
3
4
5
6
7
8
9
10
11
|
dp = [0] * 1000001
n = int(input())
dp[1] = 1
dp[2] = 2
for i in range(3, n+1) :
dp[i] = (dp[i - 1] + dp[i - 2]) % 15746
print(dp[n])
|
cs |
이전 문제인 1로 만들기 문제처럼 점화식을 그나마 찾기 쉬운 문제였지만, 여전히 아직 도출하는게 어려웠던거 같습니다.
또, 해당 문제는 점화식이 피보나치 수열의 점화식과 같기 때문에 추후에 다시 문제를 풀 때 더 빠르게 점화식을 도출 해내는데 조금이나마 도움이 될 거 같다고 느꼈습니다.
다음 포스트에서 또 다른 백준 알고리즘 문제로 포스팅하겠습니다. 감사합니다.