문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static final int DIVIDE_NUMBER = 1234567;

public int solution(int n) {
    int[] cache = new int[n+1];

    cache[1] = 1;

    for (int i = 2; i < n+1; i++) {
        cache[i] = ((cache[i-1]) % DIVIDE_NUMBER + (cache[i-2]) % DIVIDE_NUMBER) % DIVIDE_NUMBER;
    }

    int answer = cache[n];
    return answer;
}

흐름

  1. n+1 크기 배열을 생성하는데 이 때 이번 문제에서 n은 1 <= n <= 100,000 이하이다.
  2. n이 1 일땐 1을 return 해야하므로 배열 1 번째엔 1을 할당 해놓아야 한다.
  3. 2부터 n + 1 까지 반복하면서 피보나치 수열 계산하는 것 처럼 i - 1, i - 2 배열에 저장된 값을 더하는데
  4. 문제에서 1234567을 나눈 나머지 값을 return 하라고 하였으므로 % 1234567을 해준다.
  5. cache 배열에서 n 번째에 있는 값을 return하면 끝

결과

번호 속도
테스트 1 통과 (0.85ms, 52.8MB)
테스트 2 통과 (0.80ms, 52.2MB)
테스트 3 통과 (0.78ms, 51.3MB)
테스트 4 통과 (0.81ms, 53.1MB)
테스트 5 통과 (0.84ms, 52.6MB)
테스트 6 통과 (0.85ms, 50.3MB)
테스트 7 통과 (0.95ms, 52.4MB)
테스트 8 통과 (0.86ms, 50.5MB)
테스트 9 통과 (0.86ms, 52MB)
테스트 10 통과 (0.89ms, 51.4MB)
테스트 11 통과 (0.84ms, 51MB)
테스트 12 통과 (0.86ms, 52.4MB)
테스트 13 통과 (3.99ms, 52.7MB)
테스트 14 통과 (3.98ms, 50.4MB)

테스트 케이스

1
2
3
4
5
6
7
assertEquals(2, test.solution(3));
assertEquals(5, test.solution(5));
assertEquals(987, test.solution(16));
assertEquals(256379, test.solution(1234156));
assertEquals(473509, test.solution(100001));
assertEquals(1168141, test.solution(100000));
assertEquals(547662, test.solution(124126347));

참고 사이트