알고리즘 문제풀이
[백준 1904] 알고리즘 25일차 : 01타일
SiO2whocode
2020. 7. 18. 16:28
https://www.acmicpc.net/problem/1904
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이��
www.acmicpc.net
다이나믹 프로그래밍 C++
접근방법
이것도 그냥 피보나치다.
근데 입력이 1,000,000까지고 출력은 모든 이진수 개수%15746이다.
그래서 그냥 피보나치 처럼 풀어서 나눈 나머지를 출력하면 절대 값이 안나온다.
다행히 나머지를 구하는 것이라는 거
나머지를 구해야 하는거면 굳이 결과 값을 다 더하면서 갈 필요가 없다.
결과 값에서 15746로 나누어 떨어지는 만큼은 필요 없기 때문에
1부터 N까지 결과값을 저장할때 15746으로 나눈 나머지만 저장하면 된다.
소스코드
#include <iostream>
using namespace std;
int main(){
int N;
cin >> N;
int cases[1000001];
cases[1] = 1;
cases[2] = 2;
for(int i = 3 ; i <= N ; i++){
cases[i] = (cases[i-1] + cases[i-2])%15746;
}
cout << cases[N];
return 0;
}
728x90