이번 문제는 프로그래머스 사이트에 공개된 문제입니다.
문제
https://programmers.co.kr/learn/courses/30/lessons/12945
분석/설계
피보나치는 작은 범위라면 재귀 호출도 가능하고, 범위가 크다면 다이나믹 프로그래밍이 효율이 좋습니다.
10,000까지의 n의 범위를 보고 다이나믹 프로그래밍을 적용했습니다.
구현 코드
public BigInteger solution(int n) {
BigInteger[] d = new BigInteger[n+1];
d[1] = BigInteger.ONE;
d[2] = BigInteger.ONE;
for (int i = 3; i <= n; i++) {
d[i] = d[i - 1].add(d[i - 2]);
}
BigInteger T = new BigInteger("1234567");
BigInteger answer = d[n].remainder(T);
return answer;
}
정답 코드(다른 사람의 코드와 비교)
public static int solution(int n) {
int answer = 0;
//n이 3일때
//f(3) = f(1)+f(2) = 1+1 = 2이므로 숫자 초기화
int num1 = 1;
int num2 = 1;
if(n==1 || n==2) return 1;
else {
for(int i=3; i<=n; i++) {
answer = (num1+num2)%1234567;
num1 = num2;//전전수
num2 = answer;//전수
}
return answer;
}
}비교
n의 범위만 보고 결과값이 크다는 생각에 BigInteger를 적용하여 처리하였으나
1234567로 나눈 나머지를 리턴하기때문에 굳이 BigInteger를 사용하지
않아도 됩니다. 어쨌든 BigInteger로 코드 제출하여도 만점으로 채점은 됩니다.
정리
아는 문제이고 쉬운 문제라도 끝까지 문제의 조건을 잘 눈여겨봐야
필요하지 않는 코드 작성을 줄일수 있습니다.