쉬운 문제라도 문제를 푸는 방법은 다양합니다.
더 명확하고 깔끔한 문제 해결 방법을 아신다면 자유롭게 말씀해주세요.
프로그래머스 12945 피보나치 수
프로그래머스 저작권을 침해하지 않기 위해
문제 보시고 싶으시면 버튼을 눌러주세요.
답변 형식
숫자 n을 받아 n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴합니다.
풀이 조건
직접 피보나치 수열을 만들었습니다.
문제를 풀 당시에 자바를 배운지 얼마 되지 않아 단순하게 생각해서 풀었습니다.
이제와서 보니 재귀로 풀게 되면 동일한 계산으로 시간초과나 용량초과가 날 것 같습니다.
의도치 않게 DP 다이나믹프로그래밍을 했었습니다.
JAVA 정답
import java.util.*;
class Solution {
public int solution(int n) {
List<Integer> pibo = new ArrayList<>();
pibo.add(0);
pibo.add(1);
for(int i=2; i<n+1; i++) {
int sum = pibo.get(i–2)+pibo.get(i–1);
pibo.add(sum%1234567);
}
return pibo.get(n);
}
}
JAVA 정답 해설
import java.util.*;
class Solution {
public int solution(int n) {
List<Integer> pibo = new ArrayList<>();
/// 피보나치 수열을 넣어줄 리스트 선언
pibo.add(0);
/// 피보나치 수열 0항 0 입력
pibo.add(1);
/// 피보나치 수열 1항 1 입력
for(int i=2; i<n+1; i++) {
int sum = pibo.get(i–2)+pibo.get(i–1);
pibo.add(sum%1234567);
/// 피보나치 수열을 만드는 과정에서 int 배열을 벗어나는 경우가 생길 수 있어
/// 1234567을 나눈 나머지 값만 저장
}
return pibo.get(n);
}
}