[프로그래머스] 멀리뛰기

n의 경우의 수:

• n = 1일 때: 1가지 경우의 수 (1)
• n = 2일 때: 2가지 경우의 수 (1, 1), (2)
• n = 3일 때: 3가지 경우의 수 (1, 1, 1), (1, 2), (2, 1)
• n = 4일 때: 5가지 경우의 수 (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2)
• n = 5일 때: 8가지 경우의 수 (1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 2, 1), (1, 2, 1, 1), (2, 1, 1, 1), (1, 2, 2), (2, 1, 2), (2, 2, 1)

여기서 규칙을 발견할 수 있습니다:

n의 경우의 수는 (n-1)의 경우의 수 + (n-2)의 경우의 수입니다.

즉, 이 문제는 피보나치 수열 문제라는 것입니다.

피보나치란?

피보나치 수열(Fibonacci sequence)은 수학에서 나오는 수열로, 다음과 같은 규칙을 따릅니다:

• 첫 번째 항: 0 또는 1 (문제에 따라 다름)
• 두 번째 항: 1
• 세 번째 항부터는 바로 앞의 두 항을 더한 값

즉, 피보나치 수열의 n번째 항은 (n-1)번째 항과 (n-2)번째 항의 합으로 정의됩니다.

예시:

• F(0) = 0
• F(1) = 1
• F(2) = F(1) + F(0) = 1 + 0 = 1
• F(3) = F(2) + F(1) = 1 + 1 = 2
• F(4) = F(3) + F(2) = 2 + 1 = 3
• F(5) = F(4) + F(3) = 3 + 2 = 5

이 규칙을 사용하여 주어진 문제를 해결할 수 있습니다.

 

---

정답은 더보기 클릭

class Solution {
    public long solution(int n) {
        long result = 1; // 결과를 저장할 변수, 초기값은 1
        
        long n1 = 1; // 피보나치 수열에서 첫 번째 값
        long n2 = 1; // 피보나치 수열에서 두 번째 값
        
        // n번째 피보나치 수를 구하기 위한 반복문
        for (int i = 1; i < n; i++) {
            // 이전 두 값의 합을 1234567로 나눈 나머지를 결과로 저장
            result = (n1 + n2) % 1234567;
            n1 = n2; // 두 번째 값을 첫 번째 값으로 갱신
            n2 = result; // 결과 값을 두 번째 값으로 갱신
        }
        
        return result; // 최종 결과 반환
    }
}