๊ธฐ๋ก๋ฐฉ

BOJ_11444 : ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜ 6 ๋ณธ๋ฌธ

CodingTest/Java

BOJ_11444 : ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜ 6

Soom_1n 2024. 2. 12. 19:29

๐Ÿ‘‰ ๋ฌธ์ œ๋งํฌ

 

11444๋ฒˆ: ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜ 6

์ฒซ์งธ ์ค„์— n์ด ์ฃผ์–ด์ง„๋‹ค. n์€ 1,000,000,000,000,000,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค.

www.acmicpc.net



๐Ÿ”ธ ๋ฌธ์ œ ๋ถ„์„ ๐Ÿ”ธ

  • ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์„ ๊ตฌํ˜„ํ•˜๋Š”๋ฐ n์ด 1,000,000,000,000,000,000 ์œผ๋กœ ๋งค์šฐ ํฐ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

๐Ÿ”ธ ๋ฌธ์ œ ํ’€์ด ๐Ÿ”ธ

  • ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์„ ๊ตฌํ˜„ํ•˜๋Š”๋ฐ ๋ฐ˜๋ณต๋ฌธ, ์žฌ๊ท€, ๋™์  ๊ณ„ํš๋ฒ•์„ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์ง€๋งŒ, ๋งค์šฐ ํฐ n์— ๋Œ€ํ•ด์„œ๋Š” ๋ถ„ํ•  ์ •๋ณต์„ ์ด์šฉํ•œ ๊ฑฐ๋“ญ์ œ๊ณฑ์„ ์ด์šฉํ•ด์•ผํ•œ๋‹ค. ํ–‰๋ ฌ ๊ณฑ์…ˆ์„ ์ด์šฉํ•œ๋‹ค.
  • n๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜์ˆ˜๋Š” (n/2-1)๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜[k1]์™€ (n/2)๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜[k2], (n/2+1)๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜[k3], (n/2+2)๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜[k4]๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค.
    • EX ) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 (n=17)
    • k1 = 13
      k2 = 21
      k3 = 34
      k4 = 55
      987 = 13*21 + 21*34
      1597 = 13*34 + 21*55

๐Ÿ”ธ ์ฝ”๋“œ ๐Ÿ”ธ

import java.io.*;

public class Main {
    private static final int R = 1000000007;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(Long.toString(fibo(Long.parseLong(br.readLine()))[1]));
        bw.flush();
    }

    private static long[] fibo(long n) {
        if (n == 1) return new long[]{0, 1};

        long[] K = fibo(n / 2);
        long k1 = K[0];
        long k2 = K[1];
        long k3 = (k1 + k2) % R;

        long kn0, kn1;

        if (n % 2 == 0) {
            kn0 = (k1 * k1 % R + k2 * k2 % R) % R;
            kn1 = (k1 * k2 % R + k2 * k3 % R) % R;
        } else {
            long k4 = (k2 + k3) % R;

            kn0 = (k1 * k2 % R + k2 * k3 % R) % R;
            kn1 = (k1 * k3 % R + k2 * k4 % R) % R;
        }

        return new long[]{kn0, kn1};
    }
}

๐Ÿ”ธ ์ฝ”๋“œ ํ•ด์„ ๐Ÿ”ธ

  • n/2 ์—๋Œ€ํ•œ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜๋ฅผ ๊ตฌํ•ด์„œ ๊ณ„์‚ฐํ•˜๋Š” ์‹์œผ๋กœ ๋ถ„ํ•  ์ •๋ณต์„ ์‚ฌ์šฉํ•œ๋‹ค.
  • ๊ฐ’์ด ์ดˆ๊ณผํ•˜์ง€ ์•Š๋„๋ก longํ˜•์„ ์“ฐ๊ณ  R์˜ ๋‚˜๋จธ์ง€๋กœ ๊ณ„์‚ฐํ•œ๋‹ค.

๐Ÿ”ธ end ๐Ÿ”ธ

 

728x90

'CodingTest > Java' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

BOJ_1747 : ์†Œ์ˆ˜&ํŒฐ๋ฆฐ๋“œ๋กฌ  (0) 2024.02.20
BOJ_1456 : ๊ฑฐ์˜ ์†Œ์ˆ˜  (0) 2024.02.18
BOJ_1744 : ์ˆ˜ ๋ฌถ๊ธฐ  (0) 2024.02.11
BOJ_1715 : ์นด๋“œ ์ •๋ ฌํ•˜๊ธฐ  (0) 2024.02.11
BOJ_1300 : K๋ฒˆ์งธ ์ˆ˜  (0) 2024.02.05