[프로그래머스] 2 x n 타일링 C++

25 Jan 2023 in Study on Coding Test

dp를 이용하여 푸는 문제

정답제출코드

#include <string>
#include <vector>

using namespace std;

int arr[60001] = {0};

int solution(int n) {
    int answer = 0;
    
    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 3;
    
    for (int i = 4; i <= n; ++i)
        arr[i] = (arr[i-1] + arr[i-2]) % 1000000007;
    
    answer = arr[n];
    return answer;
}

워낙 유명한 문제이기도하고 백준에도 같은 문제가 있어서 쉽게 풀 수 있었다.

• n=1 일때, 1
• n=2 일때, 2
• n=3 일때, 3
• …

이렇게 진행되고, 이후에는 마치 피보나치수열처럼 i번째 가짓수는 i-1번째 가짓수 + i-2번째 가짓수로 책정이 된다.

그런데 맞왜틀을 했던 점이 1000000007로 나눈 나머지 값을 반환하라는 점을 깜빡했다는 점이다.

풀 때 문제 잘 읽고 조심하자..