lango

찍먹? 부먹?
난 부먹 개발자.

1 minute read



입출력 예시

Input-1
4
Output-1
5

Input-2
3
Output-2
3


문제 풀이

나머지연산의 시점

이 문제내용을 잘 보면 “효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수” 를 작성해야 한다고 한다. 구한 정답에서 1234567을 MOD연산하여 반환하는것이 아니라 단계마다 MOD연산을 해야 한다고 알고 있었다. 그러니 문제를 풀어가며 MOD연산을 진행하도록 하자.

피보나치 수열?

일일이 손으로 1칸, 2칸, 3칸, 4칸 … 8칸까지 정답을 구해보니, “1,2,3,5,8,13,21,34” 의 구조를 이루었다. 어디서 많이 본 수열이다 싶었는데 바로 피보나치 수열을 띄고 있었다.

아이디어 도출

나머지연산을 단계별로 수행해야 함을 알았고, 피보나치 수열의 n번째 수가 정답이라는 것을 알았다. 정리해보자.

  • 정답을 1234567로 나눈 나머지를 반환해야 한다.
    • 단계별로 1234567을 나눈 나머지를 계산해야한다.
  • 피보나치 수열과 동일한 구조를 가지고 있다.
    • 0,1,2는 n 그대로 반환하자.
    • 피보나치 수열의 n자리수를 반환하면 된다.

아이디어를 정리했으니 코드로 작성해보자.

1
2
3
4
5
6
7
8
9

int n1, n2, fibo;
n1 = 0;
n2 = 1;
fibo = 1;
for(int i=1; i<n; i++) {
    n1 = n2;
    n2 = fibo;
    fibo = (n1 + n2) % 1234567;
}

위 코드는 피보나치 수열에서 n번째 수를 구하는 과정을 작성하였다. 또한, n번째 피보나치수를 구할 때마다 1234567 나머지연산을 수행하였다.

작성한 코드를 제출하니, 모든 테스트케이스를 정상적으로 통과하였다.

작성 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        long start = System.currentTimeMillis();
        solution(n);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }
    public static long solution(int n) {
        // 1. 정답을 1234567로 나눈 나머지를 반환해야 한다. -> 단계별로 1234567을 나눈 나머지를 계산해야한다.
        // 2. 피보나치 수열과 동일한 구조를 가지고 있다. -> 0,1,2는 n 그대로 반환하자.
        // 3. 두 수의 합으로 다음 수 fibo를 만들수 있다.
        int n1, n2, fibo;
        n1 = 0;
        n2 = 1;
        fibo = 1;
        for(int i=1; i<n; i++) {
            n1 = n2;
            n2 = fibo;
            fibo = (n1 + n2) % 1234567;
        }
        return fibo;
    }
}

다름 사람의 풀이

1
2
3
4
5
6

public static long solution2(int n) {
    long answer;
    if(n <= 2) return n;
    else answer = solution2(n-1) + solution(n-2);
    return answer;
}

회고

  • 나머지연산의 시점은 잘 파악하였지만, 피보나치 수열의 구조와 같음을 꺠닫기까지 시간이 조금 걸렸다..ㅠ
  • n번째 피보나치 수를 구하는 코드를 아주 깔끔하게 작성한 다른 사람의 풀이를 보고 가독성 좋은 코드를 위해 노력해야겠다고 느꼈다.

You may also enjoy