프로그래머스 피보나치 수 c++

 

 

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

프로그래머스

#include <string>
#include <vector>

using namespace std;

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

하면서도 안될 것 같더라 ㅋㅋ

테스트 1 〉	통과 (0.01ms, 4.17MB)
테스트 2 〉	통과 (0.01ms, 4.2MB)
테스트 3 〉	통과 (0.01ms, 4.14MB)
테스트 4 〉	통과 (0.01ms, 4.14MB)
테스트 5 〉	통과 (0.01ms, 4.14MB)
테스트 6 〉	통과 (0.01ms, 4.21MB)
테스트 7 〉	실패 (0.01ms, 4.2MB)
테스트 8 〉	실패 (0.01ms, 4.14MB)
테스트 9 〉	실패 (0.01ms, 4.21MB)
테스트 10 〉	실패 (0.01ms, 4.22MB)
테스트 11 〉	실패 (0.01ms, 4.13MB)
테스트 12 〉	실패 (0.01ms, 4.13MB)
테스트 13 〉	실패 (0.28ms, 4.13MB)
테스트 14 〉	실패 (0.28ms, 3.68MB)

n의 범위는 100000이니까 무조건 1234567보다 작다. 그니까 그냥 리턴하면 된다?

테스트 1 〉	통과 (0.01ms, 3.95MB)
테스트 2 〉	통과 (0.01ms, 4.14MB)
테스트 3 〉	통과 (0.01ms, 4.22MB)
테스트 4 〉	통과 (0.01ms, 4.21MB)
테스트 5 〉	통과 (0.01ms, 4.17MB)
테스트 6 〉	통과 (0.01ms, 4.15MB)
테스트 7 〉	실패 (0.01ms, 4.2MB)
테스트 8 〉	실패 (0.01ms, 4.15MB)
테스트 9 〉	실패 (0.01ms, 4.2MB)
테스트 10 〉	실패 (0.02ms, 4.2MB)
테스트 11 〉	실패 (0.01ms, 3.67MB)
테스트 12 〉	실패 (0.01ms, 3.67MB)
테스트 13 〉	실패 (0.26ms, 4.19MB)
테스트 14 〉	실패 (0.26ms, 4.21MB)

그럴리가 없구요

오버플로우 때문이라는 단서를 얻고 매번 나눠서 더해줬다.

#include <string>
#include <vector>

using namespace std;

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

테스트 1 〉	통과 (0.01ms, 3.59MB)
테스트 2 〉	통과 (0.01ms, 4.18MB)
테스트 3 〉	통과 (0.01ms, 4.2MB)
테스트 4 〉	통과 (0.01ms, 4.35MB)
테스트 5 〉	통과 (0.01ms, 4.19MB)
테스트 6 〉	통과 (0.01ms, 4.18MB)
테스트 7 〉	통과 (0.01ms, 4.13MB)
테스트 8 〉	통과 (0.01ms, 4MB)
테스트 9 〉	실패 (0.01ms, 4.12MB)
테스트 10 〉	실패 (0.02ms, 3.58MB)
테스트 11 〉	통과 (0.01ms, 4.22MB)
테스트 12 〉	실패 (0.02ms, 4.19MB)
테스트 13 〉	통과 (0.54ms, 3.72MB)
테스트 14 〉	통과 (0.56ms, 4.11MB)

어림도 없구요

매번 더해주지 말고 더한 값이 크면 나누게 바꿔줬다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;
    for (int i = 4; i <= n; i++)
    {
        dp[i] = dp[i - 2]+ dp[i - 1];
        if (dp[i] >= 1234567)
            dp[i] %= 1234567;
    }
    return (dp[n]);
}

테스트 1 〉	통과 (0.01ms, 3.58MB)
테스트 2 〉	통과 (0.01ms, 4.12MB)
테스트 3 〉	통과 (0.01ms, 3.74MB)
테스트 4 〉	통과 (0.01ms, 4.14MB)
테스트 5 〉	통과 (0.01ms, 4.16MB)
테스트 6 〉	통과 (0.01ms, 3.67MB)
테스트 7 〉	통과 (0.02ms, 4.2MB)
테스트 8 〉	통과 (0.01ms, 4.16MB)
테스트 9 〉	통과 (0.01ms, 4.21MB)
테스트 10 〉	통과 (0.02ms, 4.21MB)
테스트 11 〉	통과 (0.01ms, 3.57MB)
테스트 12 〉	통과 (0.01ms, 3.69MB)
테스트 13 〉	통과 (0.63ms, 4.2MB)
테스트 14 〉	통과 (0.62ms, 4.13MB)

편 ㅡ안