백준 1904번 : 01타일

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

1904번: 01타일

 

이 문제는 실버 3 문제이고 다이나믹 알고리즘을 통해 부는 것이다.

엄청 오랜만에 알고리즘 문제를 보니 순간 머리가 띵햇다...

진짜 엄청 고민한거 같넹... (이제 부터 스프링 공부랑 병행하면서 해야할듯욤..)

일단 사실 피보나치랑 같은 개념이다.  천천히 생각해보자 (뒤에만 타일을 붙인다고 해도 무방) 괜히 앞에다가 붙이고 복잡하게 생각하지말자... 

조건 1. 00타일만 붙일 수 있다.

조건 2 , 1 타일만 붙일 수 있다.

즉 f(n) 이 할 수 있는 모든 타일 갯수라고 했을 때

조건 1은 f(n-2) 에서 적용이 가능하고  여기서 f(n-1)도 모든 타일 갯수 즉 최적의 해다. 

조건 2는 f(n-1) 에서 적용이 가능하다. 여기서 f(n-1)도 모든 타일 갯수 즉 최적의 해다.

고로 f(n) = f(n-1)+f(n-1) 이다 물론 이런 재귀는 부담되는 연산이 되므로 메모라이징으로 계산된 값을 기억하자

이제 코드를 보자

#include <iostream>
using namespace std;
int d[1000001];

int fibonacci(int n){
    if(d[n]!=0){
        return d[n];
    }
    if(n<=1){                     //1일 떄는 타일 갯수 1  
        d[1]=1;
        return d[1];
    }
    if(n==2){                 //2일떄는 타일 갯수 2
        d[2]=2;
        return d[2];
    }
    d[n]=(fibonacci(n-1)+fibonacci(n-2))%15746;      //피보나치 수열이랑 똑같음
    return d[n];
}
int main(){
    int t;
    cin>> t;
    int ans = fibonacci(t)%15746;
    cout <<ans;
}