https://www.acmicpc.net/problem/1904
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수
www.acmicpc.net
N=1, 2일때와 N이 커질경우 int 범위를 넘는다는 것만 고려하면 매우 쉽게 풀린다. 그냥 피보나치:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <cstdio>
int main(void){
int N;
scanf("%d",&N);
int cnt1=1, cnt2=2, cnt3;
if(N<3) cnt3 = (N == 1) ? 1 : 2 ;
else{
N=N-2;
while(N--){
cnt3=(cnt1 + cnt2)%15746;
cnt1=cnt2;
cnt2=cnt3;
}
}
printf("%d",cnt3);
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">c |
'알고리즘 문제' 카테고리의 다른 글
| [C/C++ 백준 11727번] 2×n 타일링 2 (Silver 3) (0) | 2020.05.06 |
|---|---|
| [C/C++ 백준 11726번] 2×n 타일링 (Silver 3) (0) | 2020.05.06 |
| [C/C++ 백준 1699번] 제곱수의 합 (Silver 3) (0) | 2020.05.05 |
| [C/C++ 백준 1912번] 연속합 (Silver 2) (0) | 2020.05.05 |
| [C/C++ 백준 2193번] 이친수 (Silver 3) (0) | 2020.05.05 |