백준 알고리즘 1904번: 01타일(Python)

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

1904번: 01타일

---

문제 해결을 위한 과정

이 문제의 경우 규칙성을 파악하면 쉽게 해결할 수 있는 문제였습니다. 또한 간단한 확률/통계에 관한 지식이 있다면 더욱 쉽게 해결할 수 있는 문제였습니다. 각각 n의 경우에 따라 계산해봅시다.

 

n = 1인 경우 1 -> 총 1개

n = 2인 경우 11, 00  -> 총 2개

n = 3인 경우 111, 100, 001 -> 총 3개

n = 4인 경우 1111, 1100, 1001, 0011, 0000 -> 총 5개

n = 5인 경우 11111, 11100, 11001, 10011, 00111, 10000, 00100, 00001 -> 총 8개

n = 6인 경우 111111, 110000, 100100, 100001, 000011, 001100, 001001, 111100, 111001, 110011, 100111, 001111, 000000 -> 총 13개

 

즉 피보나치수열의 형태를 띄고 있는 것을 알 수 있습니다. 따라서 점화식은 다음과 같습니다.

dp [i] = dp [i-1] + dp [i-2]

---

이번 문제부터 소스코드를 파이썬, C++ 두 가지 형태로 업로드할 계획입니다. 

소스코드 - python

n = int(input())
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
 
for i in range(2, n+1):
  dp[i] = dp[i-1] + dp[i-2]
 
print(dp[n-1])

---

소스코드 - C++

#include <bits/stdc++.h>
 
using namespace std;
 
int main(void) {
  int n;
  scanf("%d", &n);
  int dp[1000001] = {0};
 
  dp[0] = 1;
  dp[1] = 2;
  for(int i = 2; i < n+1; i++) {
    dp[i] = (dp[i-1] + dp[i-2])%15746;
  }
 
  printf("%d\n", dp[n-1]);
 
  return 0;
}