오늘의 문제
2xn 타일링
문제 분석
- 이전에 프로그래머스에서 풀어봐서 그런것 같기도 하지만, 처음 풀었을 때 전혀 어떻게 풀어야할 지 몰랐는데 풀이방법을 바로 생각할 수 있었다. 경험치가 쌓인것 같긴 하다.
- n을 만들어야하는 숫자로 보고, 연산을 1, 2만 할 수 있다고 생각하면, 피보나치인것을 알 수 있다. 연산이 1, 2, 3 이런식으로 되어있는건 거의 이런 방식으로 문제가 풀린다.
나의 풀이
#include <iostream>
using namespace std;
int n;
const int DIV = 10007;
// 2xn 타일링
int solution(){
int fib[] = {1, 2};
if(n < 3)
return fib[n-1];
for(int i=3;i<=n;i++){
int sum = fib[0] + fib[1];
fib[0] = fib[1];
fib[1] = sum%DIV;
}
return fib[1];
}
다른 답안
#include <cstdio>
int main()
{
int n, temp1=0,temp2=1,ans;
for(scanf("%d",&n); n--;)
ans=(temp1%10007+temp2%10007)%10007, temp1=temp2, temp2=ans;
printf("%d",ans);
}
배울 점