https://www.acmicpc.net/problem/1904
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 규칙성을 파악하면 쉽게 해결할 수 있는 문제였습니다. 또한 간단한 확률/통계에 관한 지식이 있다면 더욱 쉽게 해결할 수 있는 문제였습니다. 각각 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
|
1
2
3
4
5
6
7
8
9
|
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])
|
cs |
소스코드 - C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#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;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 11057번: 오르막 수(Python) (0) | 2022.01.29 |
|---|---|
| 백준 알고리즘 9251번: LCS(Python) (0) | 2022.01.29 |
| 백준 알고리즘 2156번: 포도주 시식(Python) (0) | 2022.01.25 |
| 백준 알고리즘 1912번: 연속합(Python) (0) | 2022.01.25 |
| 백준 알고리즘 1149번: RGB거리(Python) (0) | 2022.01.24 |