백준 알고리즘 1904 (01타일) - C++, Python

[문제] 백준 알고리즘 1904 (01타일)

> https://www.acmicpc.net/problem/1904

1904번: 01타일

2진 수열에서, 0을 하나만 못 쓰고 0을 짝수 개로 쓸 수 있을 때, n의 2진 수열은 몇 개인가를 구하는 문제.

(값에서 15746으로 나눈 나머지를 출력한다)

 

N	2진 수열	갯수
1	1	1
2	1 00	2
3	111 100 001	3
4	1111 1100 1001 0011 0000	5
5	11111 11100 11001 10011 10000 00100 00001	8

딱 보자마자 피보나치 수가 떠올랐다. DP를 위해 점화식을 세워서 해결하면 되겠다.

 

[문제 해결]

1. N 입력, N의 MAX는 1000000이므로 dp[MAX+1] 선언

    - dp[1] = 1, dp[2] = 2

2. dp[3]부터 피보나치 점화식을 사용해서 DP 진행

    - dp[n] = (dp[n-1] + dp[n-2]) % 15746

    - 15746의 나머지를 출력하기 위함, 아마 int로 제한하기 위함 같음

    - for문을 3~N까지 반복하며 점화식 진행

3. dp[n] 출력

 

[C++]

#include <cstdio>
using namespace std;
const int MAX = 1000000;
int n, mod = 15746, dp[MAX + 1];

int main() {
	scanf("%d", &n);
	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
	}
	printf("%d", dp[n]);
	return 0;
}

 

[Python]

import sys
input = sys.stdin.readline
n = int(input())
MAX = 1000000
dp = [0 for _ in range(MAX+1)]
mod, dp[1], dp[2] = 15746, 1, 2
for i in range(3, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % mod
print(dp[n])