(C++) - 백준(BOJ) 2346번 : 풍선 터뜨리기 답

www.acmicpc.net/problem/1904

1904번: 01타일

간단한 dp문제였습니다.

 

풀이방법

1. 00타일 : 길이 2

   1타일 : 길이 1 인 정보를 가지고 있습니다.

  길이[i-1]인 타일을 만들 수 있는 경우의 수 = 다음에 1타일을 연결하면 길이 i가 됩니다. => 1타일사용

  길이[i-2]인 타일을 만들 수 있는 경우의 수 = 다음에 00타일을 연결하면 길이 i가 됩니다. => 00타일사용

 

  따라서 길이 i인 타일을 만들 수 있는 경우의 수 = 길이[i-1]인 타일을 만들 수 있는 경우의 수 + 길이[i-2]인 타일을 만들 수 있는 경우의 수 입니다. 

  

2. %(modula)연산 분배법칙이 성립하여 + 뒤 마지막에만 15746을 나누면 답이 됩니다.

 

Code

#include <iostream>
#define ll long long
using namespace std;
int n;
ll d[1000001] = {0,1,2,};
int main(){
    cin >> n;
    for(int i = 3; i <= n; i++)
        d[i] = (d[i-1] + d[i-2]) % 15746;
    cout << d[n] << '\n';
}