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

 

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

 

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

---

 

 

해결방안

 

동적 계획법 Dynamic Programming (DP)

피보나치 Fibonacci

---

 

처음 시도한 코드

 

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

int solution(int n) {
    int answer = 0;

    vector<int> dp(60001, 0);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;

    for(int i=4; i<=n; i++){
        dp[i] = dp[i - 2] + dp[i - 1];
    }
    
    answer = dp[n] % 1000000007;

    return answer;
}

 

 

answer = dp[n] % 1000000007;

dp 연산 후 나머지 연산을 수행해서 전부 실패가 나왔다.

그래서 점화식을 잘못 짠줄알고 한참 찾았다..

 

 dp[i] = (dp[i - 2] + dp[i - 1]) % 1000000007;

위의 코드처럼 연산 중간에 나머지 연산을 수행하면 정답이 된다. 

dp 연산 중간에 나머지 연산을 넣어야 한다.

아.. 이건 너무한거 아니냐고...

---

 

정답 코드

 

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

int solution(int n) {

    vector<int> dp(60001, 0);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;

    for(int i=4; i<=n; i++){
        dp[i] = (dp[i - 2] + dp[i - 1]) % 1000000007;
    }

    return dp[n];
}

 

 

 

---