[프로그래머스] 피보나치 수 (java) Recursion
2020-01-24
피보나치 수(programers > lev2 > Recursion)
문제설명
피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
예를들어
- F(2) = F(0) + F(1) = 0 + 1 = 1
- F(3) = F(1) + F(2) = 1 + 1 = 2
- F(4) = F(2) + F(3) = 1 + 2 = 3
- F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.
2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.
제한 사항
- n은 1이상, 100000이하인 자연수입니다.
입출력 예
| n | return |
|---|---|
| 3 | 2 |
| 5 | 5 |
입출력 예 설명
피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, … 와 같이 이어집니다.
풀이
//시간 초과........!! (답은 맞음)
static public int fib(int n) {
int answer = 0;
if(n == 0)
return 0;
if(n == 1)
return 1;
answer = fib(n-1)%1234567 + fib(n-2)%1234567;
return answer %1234567;
}
static public int solution(int n) {
int answer = 0;
if(n == 1)
return 1;
int a = 0; // n-1 값 넣기
int b = 1; // n-2 값 넣기
for(int i=2; i<=n; i++) {
answer = a + b;
a = b% 1234567;
b = answer% 1234567;
} // a= b; b = a+b; 를 하니까 b = b+b 가 되었는데.. 그것도 모르고 계속 저렇게 함...
return answer % 1234567;
}
public static void main(String[] args) {
System.out.println(solution(3));
System.out.println(fib(3));
}
후기 (20min)
a와 b가 반복되는 부분에서 뭘 변수로 넣어줘야 하는지 헤매다가 시간이 훌쩍 지나버렸다..허허 이렇게 쉬운 문제도 안풀다가 다시 풀면 까먹는 불상사가..
또, 재귀로 풀면 큰 수 일 경우에 같은 숫자도 여러번 반복하기 때문에 시간초과가 뜬다. for문은 전 값과, 전전 값을 가지고 있기 때문에 시간초과가 뜨지않고 문제를 해결할 수 있었다!
tip
- 재귀로 풀때 시간초과가 뜨는 문제는 dp로 풀어야하기 때문에 생각을 잘 해줘야 할것 같다!
- 피보나치 까먹지말자! 변수에 뭘 넣고 반복해줘야 하는지도!