[프로그래머스] 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
이번 문제를 풀면서 모듈러 연산의 성질을 알게 되었고, 앞으로 문제 풀때 아이디어로 활용해야겠다.
Author And Source
이 문제에 관하여([프로그래머스] Q.12945_C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jooyeon/프로그래머스-Q.12945C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)