[프로그래머스] Q.12945_C++

1. 문제-풀이

(1) 문제

(2) 풀이

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    if(n<2) answer = n%1234567;
    else{
        int temp = 0;
        int a=0;
        int b=1;
        for(int i=0;i<n-1;i++){
            temp = a;
            a=b;
            b=temp%1234567+a%1234567;
        }
        answer = b%1234567;
    }
    return answer;
}

2. 틀린이유

처음에 별 생각없이 재귀함수로 작성해서 제출했는데 시간 초과로 나왔다. 구글링 해보니까 재귀함수는 O(n^2)이 걸려서 오래걸리기 때문에 더 효율적인 방법을 찾아야 했다.

반복문은 O(n)이 걸리길래, 우선 반복문으로 다시 시도해봤는데 또 틀렸다.

생각해보니 int 자료형의 크기는 정해져있기 때문에 빠른 속도로 커지는 피보나치 수열은 당연히 범위를 넘어서서 오버플로우가 발생하니까 틀린것이다.

전에도 자료형의 범위를 생각안했다가 틀린적이 여러번이었는데, 또 틀렸기 때문에 이제 아주 각인 시켜서 자료형의 범위는 항상 확인을 해야겠다.

3. 새로 배운점

int형의 범위를 넘지 말아야겠다는건 알았는데, 어떻게 처리해줘야 할까 생각하다가 문제에서 1234567로 나눈 나머지를 제시한 이유를 생각해보니 애초에 자료형 범위를 안넘게 힌트를 주고 있다는 걸 알았다.

하지만 모듈러 연산 성질을.. 모르고 있었기 때문에 구글링 도움을 받았다.

// 내가 사용하고자 한 성질은 아래와 같다.
(A+B) % C = ((A%C) + (B%C)) % C

이 성질을 이용하면 이렇게 생각할 수 있다.

F(n) % 1234567
= ( F(n-1) % 1234567 + F(n-2) % 1234567 ) % 1234567

이번 문제를 풀면서 모듈러 연산의 성질을 알게 되었고, 앞으로 문제 풀때 아이디어로 활용해야겠다.