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

프로그래머스 멀리 뛰기 문제를 잘 보면 재미있는 규칙이 나온다.

 

k가 1과 2로 이루어진 배열일 때 f(k)는 k 배열 속에 있는 1과 2를 나열하는 함수라고 해보자.

이때 동일한 숫자끼리 자리가 바뀌어도 하나의 경우의 수로 본다. 그러면

n = 1일 때, 

f([1]) = 1

 

n = 2일 때, 

f([2]) + f[1] = 2  

 

n = 3일 때,

f([1, 1, 1]) + f[1, 2] = 1 + 2 = 3

 

n = 4일 때,

f([1, 1, 1, 1]) + f[1,1, 2] + f[2, 2] = 1 + 3 + 1 = 5

 

n = 5일 때,

f([1, 1, 1, 1, 1]) + f[1,1, 1, 2] + f[1, 2, 2] = 1 + 4 + 3 = 8

 

n = 6일 때,

f([1, 1, 1, 1, 1, 1]) + f[1, 1, 1, 1, 2] + f[1, 1, 2, 2]  + f[2, 2, 2]  = 1 + 5 + 6 + 1 = 13

 

n = 7일 때,

f([1, 1, 1, 1, 1, 1, 1]) + f[1, 1, 1, 1, 1, 2] + f[1, 1, 1, 2, 2]  + f[1, 2, 2, 2]  = 1 + 6 + 10 + 4 = 21

 

이런 방식으로 증가한다.

이는 피보나치 수열과 동일한 방식으로 증가하기 때문에 n = k일 때 수는 n번째 피보나치 수열과 같다.

그런데 문제에서 요구하는 것은 k번 째 피보나치 수열을 1234567로 나눈 나머지이다. 이때 k번째까지 더한 후

mod 연산을 시도하면 long타입을 넘어가게 된다. 이를 방지하기 위해 모든 피보나치 수열에 해대 1234567로 나눈 후

더해준다. 원리는 다음과 같다.

a, b는 음이 아닌 정수이고 r1과 r2는 임의의 피보나치 수를 1234567로 나눈 나머지라고 했을 때 k-2 번째 피보나치 수열은 a * 1234567 + r1으로 나타낼 수 있고 k - 1번째 피보나치 수열은 b * 1234567 + r2로 나타낼 수 있다. 이때 우리가 구하고자 하는 k번 째 피보나치 수열은 다음과 같이 나타낼 수 있다.

즉, 계속해서 피보나치 수열을 더해 r1 + r2가 1234567을 넘어도 (a + b + 1) * 1234567 + r1 + r2 형태로 나타낼 수 있고 우리가 원하는 것은 피보나치 수를 1234567로 mod연산(% 연산)하여 (a + b) * 1234567을 없앤 r1 + r2 부분이기 때문에 피보나치 수를 모두 더하고 1234567로 나누는 것과 피보나치 수를 1234567로 나눈 나머지를 더해주는 것은 같은 결과가 나온다.

 

소스코드

class Solution {
    public long solution(int n) {
        
        long a = 0;
        long b = 1;
        long answer = 0;
        
        for(int i = 1; i <= n; i++) {
            answer = (a + b) % 1234567;
            a = b;
            b = answer;
        }
        
        return answer;
    }