[프로프래머스 2*n타일링] c++ (코드,풀이)

문제 링크

 

https://school.programmers.co.kr/learn/courses/30/lessons/12900

프로그래머스

 

문제

 

풀이 및 코드

 

v[i] = v[i-1] + v[i-2]였던 문제입니다. 왜냐하면 

 

마지막 끝은 가로로 끝나거나 세로로 끝나는 것 두가지 케이스 밖에 없기 때문입니다.

1-> 1

2 -> 2

3 -> 3

4 -> 5

5 ->

n번째 칸은? -> n-1번째 에서 세로 + n - 2번째 칸 가로가로/세로세로 가 아닐까 생각

하지만! n-2칸의 세로세로는 n-1칸에 포함이 됨.

즉, v[i] = v[i-1] + v[i-2]라고 추측

는 아니었음 그렇게 간단할리가ㅋㅋ

응? 맞네..? 나머지를 안해서 그렇네

나머지를 안하면 모든 테케에서 틀리게 해가지고 내가 틀렸나.. 하면서 다른 풀이로 했다가 시간 초과가 뜨길래 이건 아무리 봐도 dp가맞는데 왜이러지.. 하면서 나머지를 아무생각없이 넣는순간 해결되었습니다. (좀 너무한듯)

 

#include <string>

#include <vector>

using namespace std;

int solution(int n) {

    int answer = 0;

   

    vector<int> v;

   

    v.push_back(1);

    v.push_back(2);

   

    for(int i =2;i<n;i++){

        v.push_back((v[i-1] + v[i-2]) % 1000000007);

    }

    return v[n-1];

}