Tags
- ๋ฐฑํธ๋ํน
- ๊ต์ฌ
- dfs
- ๋ฌธ์์ด
- Study
- Brute Force Algorithm
- LV2
- BFS
- ๊ทธ๋ํ ์ด๋ก
- ๊น์ด ์ฐ์ ํ์
- DP
- ๊ตฌํ
- PGM
- queue
- ๋๋น ์ฐ์ ํ์
- greedy
- CodingTest
- ์ ์๋ก
- Java
- Dynamic Programming
- ์ ๋ ฌ
- stack
- sort
- ๊ทธ๋ํ ํ์
- BOJ
- SpringBoot
- ์๋ฃ๊ตฌ์กฐ
- ์๋ฎฌ๋ ์ด์
- Python
- ์ํ
Archives
๊ธฐ๋ก๋ฐฉ
BOJ_11444 : ํผ๋ณด๋์น ์ 6 ๋ณธ๋ฌธ
๐ธ ๋ฌธ์ ๋ถ์ ๐ธ
- ํผ๋ณด๋์น ์์ด์ ๊ตฌํํ๋๋ฐ 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 |