[프로그래머스][Java] 피보나치 수 - level 2

문제 보기

https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

 

 

문제

피보나치 수는 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은 2 이상 100,000 이하인 자연수입니다.

 

 

풀이방법

처음에는 피보나치라면 이거지 하고 정석적인 풀이인 재귀함수로 구현했지만 시간 초과가 났다.

이거 재귀함수 때문이구나 하는 생각이 들었지만 뭔가 딱 아이디어가 떠오르지는 않았다.

 

그런데 아래에 힌트 모음집이라는 링크가 보여서 한 번 클릭해 봤다.

https://school.programmers.co.kr/learn/courses/14743/14743-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%97%B0%EC%8A%B5-%ED%9E%8C%ED%8A%B8-%EB%AA%A8%EC%9D%8C%EC%A7%91?itm_content=lesson12945

코딩테스트 연습 힌트 모음집

 

오 이거 한 번 정독하면 좋을 것 같은데?

그래서 내가 겪었던 상황인 7~14번 테스트 케이스에서 "시간 초과" OR "런타임 에러"로 링크를 타고 들어가니

"다이나믹 프로그래밍" 이라는 글자만 딱 눈에 들어왔다.

그 뒤로 얼씨구나 하고 풀었다. ㅋㅋ

 

 

전체 코드 & 주석

class Solution {
    public int solution(int n) {
        int answer = 0;

        int[] dp = new int[n + 1]; // dp 계산 수행할 배열 생성
        dp[0] = 0; // 피보나치 0일 때는 0
        dp[1] = 1; // 피보나치 1일 때는 1
        for(int i = 2; i <= n; i++) // 입력값일 2부터 n까지
        {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567; // F(n) = F(n-1) + F(n-2) 그리고 모드연산
        }
        answer = dp[n]; // 답은 n일 때
        return answer;
    }
}

 

 

풀이 GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/12945.%E2%80%85%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%E2%80%85%EC%88%98

CodingTest_AutoSave/프로그래머스/2/12945. 피보나치 수 at main · MetroDefro/CodingTest_AutoSave