티스토리 뷰

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;
}
댓글
댓글쓰기 폼