[백준 17840번] 피보나치 음악

문제 링크: 17840번 피보나치 음악

https://www.acmicpc.net/problem/17840

 

N번째 수에 바로 접근하는 방법

나누는 수는 2 이상으로 정해져있는데, 그렇다면 나머지를 저장하는 수열은 반드시 0 1 1 ... 이런 식으로 이루어진다. 그렇다면 저 패턴이 다시 반복되면, 해당 패턴은 무한히 반복되는 것이다. 수열을 만들어가면서 1 1이 반복되면 그 때 멈추면 된다.

 

한 자리씩 떼어내서 세는 것을 어떻게 해야할까?

fibo 배열과 digitList 배열을 따로 두어서 해결할 수 있다.

 

조심해야 할 점

아무 생각없이 나누면서 리스트에 집어넣어버리면 1의 자리부터 역순으로 들어가게 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int q = Integer.parseInt(st.nextToken()); // 질의 개수
        int m = Integer.parseInt(st.nextToken()); // 나누는 수
        long[] nums = new long[q];
        long maxN = -1;
        for (int i = 0; i < q; i++) {
            nums[i] = Long.parseLong(new StringTokenizer(br.readLine()).nextToken());
            if (maxN < nums[i]) {
                maxN = nums[i];
            }
        }

        StringBuilder sb = new StringBuilder();

        ArrayList<Integer> fibo = new ArrayList<>();
        ArrayList<Integer> digitList = new ArrayList<>();

        fibo.add(0); digitList.add(0);
        fibo.add(1); digitList.add(1);
        fibo.add(1); digitList.add(1); // fibo[1] = 1, fibo[2] = 1

        long patternLen = 0;
        for (int i = 3; i <= maxN + 1; i++) {
            int curFibo = (fibo.get(i-1) + fibo.get(i-2) ) % m;
            fibo.add(curFibo);

            int curFibo_ = curFibo;

            if (curFibo == 0) {
                digitList.add(0);
            }

            ArrayList<Integer> temp = new ArrayList<>();
            while (curFibo_ > 0) {
                temp.add(curFibo_ % 10);
                curFibo_ /= 10;
            }
            for (int t = temp.size() - 1; t >= 0; t--) {
                digitList.add(temp.get(t));
            }

            if (i > 2 && fibo.get(i) == 1 && fibo.get(i-1) == 1) {
                patternLen = digitList.size() - 3;
                break;
            }
        }

        digitList.remove(0);

        for (long num : nums) {
            int idx;
            if (patternLen != 0) {
                idx = (int)((num-1) % patternLen);
            }
            else {
                idx = (int)((num-1));
            }
            sb.append(digitList.get(idx)).append('\n');
        }

        System.out.print(sb);
    }
}