#1904 01타일

https://www.acmicpc.net/problem/1904

1904번: 01타일

실버 3의 문제였다. 문제는 굉장히 어려워보였는데 끄적끄적하니까 쉬웠다. 처음에는 이걸 직접 구하면서 카운트하는 변수를 하나씩 더해야하나? 이생각을 했었는데 dp의 방법이 전혀 아닌거같았다. dp인건 어떻게 알았냐면, 사실 dp탭으로 들어와서 알기는 했는데 제한시간이 0.75초 이면 무지~~엑건 dp문제인거 같았다. 암튼!

 

#include <iostream>
#include <vector>
using namespace std;

long long memo[1000001];

int main()
{
  int N;
  cin>>N;
  memo[1]=1;
  memo[2]=2;

  for(int i=3;i<=N;i++){
    memo[i]=(memo[i-1]+memo[i-2])%15746;
  }

  cout<<memo[N];
}

정답 코드는 위와같다. 일단 long long을 써야 하는 것에서부터 당황쓰 했다. N이 4일때, 5일때, 6일때를 차근차근히 구해서 개수를 세보니까 피보나치 수열의 수와 같았다. 근데 내가 좀 초보티가 났던게, 피보나치 함수를 구현해서 그거를 쓸 생각을 했다. 그게아니고, 어차피 피보나치 수열의 점화식이 fibo(N) = fibo(N-1) + fibo(N-2) 이기 때문에, 이를 그냥 그대로 사용하면 되는 것이었다. 위의 코드와 같이 말이다.

 

또 백만정도의 수를 피보나치 수열로 돌리면, long long의 제한보다 큰 수가 나온다고 한다. 따라서 문제에서는 15746으로 나눈 나머지를 구하라고했고, 원래 맨마지막에 cout부분에서 나누려고했으나, 그렇게 하면 이미 그 거대한 수를 구한다음에 나누는것 이기 때문에 문제가 그대로 드러날 것이라 판단하여 for문 안에서 계산하자마자 바로 나누어버렸다.

 

롱롱과 피보나치수열에 대한 무지함에서 나온 어려움이었다. 😢