문제

정답 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        long[] longs = new long[n+1];

        longs[0]=0;
        longs[1]=1;

        for (int i=2;i< longs.length;i++) {
            longs[i]=(longs[i-1]+longs[i-2])%1234567;
        }

        answer=(int) (longs[n]%1234567);
        
        return answer;
    }
}

처음엔 int로 선언해서 풀었다가 범위가 넘어가는 듯 해서 long으로 바꿨다.

그런데도 오답이 나와서 다른 사람의 풀이를 참고했는데, 다들 숫자를 계산할때마다 1234567의 나머지를 적용하는게 아닌가!? 왜..? n번째에만 적용해서 return하면 되는거 아닌가?? 이해되지 않았다. 처음엔 문제가 잘못되었나 싶었다.

하지만 스터디에서 피보나치수가 long 도 넘어가는 무지막지한 크기를 자랑한다는것을 알게되었다. 그래도 왜 저렇게 하는지 이해가 안되었었는데, 수학 공식을 적용시켜보니 이해가 되었다.

n+2번째 수를 a로 나눈 나머지는 n+1번째 수와 n번째 수를 a로 나눈 나머지를 합한 것과 같다.

또한 스터디 조원분들이 재귀호출, DP 등 생소한 단어들을 소개해주셔서 그것을 공부해보았다. 단어는 생소하지만 내가 알게모르게 잘 쓰고 있던 방식들의 이름이었다.

동적계획법 (Dynamic Programming, DP)

DP는 "동적 계획법(Dynamic Programming)"의 약어로, 최적화 문제를 해결하기 위한 수학적 최적화 기법 중 하나입니다. 이 방법은 큰 문제를 작은 하위 문제로 나누어 해결함으로써 전체 문제를 해결하는 것을 목표로 합니다.

재귀호출(Recursion)

재귀 호출(Recursion)은 함수가 자기 자신을 직접 또는 간접적으로 호출하는 프로그래밍 기법을 나타냅니다. 재귀는 주로 큰 문제를 해결하기 위해 같은 종류의 더 작은 문제로 분할하는데 사용됩니다. 이런 작은 문제들은 다시 동일한 방법으로 해결되거나 결합하여 전체 문제를 해결하는 데 사용됩니다.