๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/6064
- ์ต๊ทผ์ ICPC ํ์ฌ๋๋ ๋จ์๋ฉ๋ฆฌ์นด์ ์์นด ์ ๊ตญ์ด ๋๋ผ์ด ๋ฌธ๋ช ์ ์ง๋ ์นด์ ์ ๊ตญ์ ํ ๋๋ก ํ์ฌ ์ธ์์ก๋ค๋ ์ฌ์ค์ ๋ฐ๊ฒฌํ๋ค. ์นด์ ์ ๊ตญ์ ๋ฐฑ์ฑ๋ค์ ํน์ดํ ๋ฌ๋ ฅ์ ์ฌ์ฉํ ๊ฒ์ผ๋ก ์๋ ค์ ธ ์๋ค.
- ๊ทธ๋ค์ M๊ณผ N๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ๋ ๊ฐ์ ์์ฐ์ x, y๋ฅผ ๊ฐ์ง๊ณ ๊ฐ ๋ ๋๋ฅผ <x:y>์ ๊ฐ์ ํ์์ผ๋ก ํํํ์๋ค.
- ๊ทธ๋ค์ ์ด ์ธ์์ ์์ด์ ํด๋นํ๋ ์ฒซ ๋ฒ์งธ ํด๋ฅผ <1:1>๋ก ํํํ๊ณ , ๋ ๋ฒ์งธ ํด๋ฅผ <2:2>๋ก ํํํ์๋ค. <x:y>์ ๋ค์ ํด๋ฅผ ํํํ ๊ฒ์ <x':y'>์ด๋ผ๊ณ ํ์.
- ๋ง์ผ x < M ์ด๋ฉด x' = x + 1์ด๊ณ , ๊ทธ๋ ์ง ์์ผ๋ฉด x' = 1์ด๋ค.
- ๊ฐ์ ๋ฐฉ์์ผ๋ก ๋ง์ผ y < N์ด๋ฉด y' = y + 1์ด๊ณ , ๊ทธ๋ ์ง ์์ผ๋ฉด y' = 1์ด๋ค. <M:N>์ ๊ทธ๋ค ๋ฌ๋ ฅ์ ๋ง์ง๋ง ํด๋ก์, ์ด ํด์ ์ธ์์ ์ข ๋ง์ด ๋๋ํ๋ค๋ ์์ธ์ด ์ ํด ์จ๋ค.
- ์๋ฅผ ๋ค์ด, M = 10 ์ด๊ณ N = 12๋ผ๊ณ ํ์. ์ฒซ ๋ฒ์งธ ํด๋ <1:1>๋ก ํํ๋๊ณ , 11๋ฒ์งธ ํด๋ <1:11>๋ก ํํ๋๋ค. <3:1>์ 13๋ฒ์งธ ํด๋ฅผ ๋ํ๋ด๊ณ , <10:12>๋ ๋ง์ง๋ง์ธ 60๋ฒ์งธ ํด๋ฅผ ๋ํ๋ธ๋ค.
- ๋ค ๊ฐ์ ์ ์ M, N, x์ y๊ฐ ์ฃผ์ด์ง ๋, <M:N>์ด ์นด์ ๋ฌ๋ ฅ์ ๋ง์ง๋ง ํด๋ผ๊ณ ํ๋ฉด <x:y>๋ ๋ช ๋ฒ์งธ ํด๋ฅผ ๋ํ๋ด๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ๋ผ.
- ์ ๋ ฅ ๋ฐ์ดํฐ๋ ํ์ค ์ ๋ ฅ์ ์ฌ์ฉํ๋ค. ์ ๋ ฅ์ T๊ฐ์ ํ ์คํธ ๋ฐ์ดํฐ๋ก ๊ตฌ์ฑ๋๋ค.
- ์ ๋ ฅ์ ์ฒซ ๋ฒ์งธ ์ค์๋ ์ ๋ ฅ ๋ฐ์ดํฐ์ ์๋ฅผ ๋ํ๋ด๋ ์ ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ ์คํธ ๋ฐ์ดํฐ๋ ํ ์ค๋ก ๊ตฌ์ฑ๋๋ค.
- ๊ฐ ์ค์๋ ๋ค ๊ฐ์ ์ ์ M, N, x์ y๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) ์ฌ๊ธฐ์ <M:N>์ ์นด์ ๋ฌ๋ ฅ์ ๋ง์ง๋ง ํด๋ฅผ ๋ํ๋ธ๋ค.
- ์ถ๋ ฅ์ ํ์ค ์ถ๋ ฅ์ ์ฌ์ฉํ๋ค. ๊ฐ ํ ์คํธ ๋ฐ์ดํฐ์ ๋ํด, ์ ์ k๋ฅผ ํ ์ค์ ์ถ๋ ฅํ๋ค.
-
์ฌ๊ธฐ์ k๋ <x:y>๊ฐ k๋ฒ์งธ ํด๋ฅผ ๋ํ๋ด๋ ๊ฒ์ ์๋ฏธํ๋ค. ๋ง์ผ <x:y>์ ์ํด ํํ๋๋ ํด๊ฐ ์๋ค๋ฉด, ์ฆ, <x:y>๊ฐ ์ ํจํ์ง ์์ ํํ์ด๋ฉด, -1์ ์ถ๋ ฅํ๋ค.
์์ด๋์ด
- ์นด์ ๋ฌ๋ ฅ์ ๊ธฐ์ค ์๊ฐ์ธ M๊ณผ N์ ์ต์๊ณต๋ฐฐ์๋ฅผ ๊ตฌํด์ค๋ค. (์ ํด๋ฆฌ๋ ํธ์ ๋ฒ์ ์ด์ฉํ์ฌ)
- ๊ทธ๋ฆฌ๊ณ i๊ฐ์ (x - 1)๊ฐ์ผ๋ก ์์์ ์ ์ก๊ณ ์ต์๊ณต๋ฐฐ์ ์ ๊น์ง M๋งํผ ์ฆ๊ฐ์ํค๋ฉด์ ๋ฐ๋ณตํ๋ค. ((x - 1)๊ฐ์ ์์์ ์ผ๋ก ์ก๋ ์ด์ ๋ ์ต์๊ณต๋ฐฐ์์ ์์์ ์ด ๊ฐ์ ์ซ์์ผ ๊ฒฝ์ฐ, ๋ฐ๋ณต๋ฌธ ์์ฒด๊ฐ ๋์๊ฐ์ง ์๊ธฐ ๋๋ฌธ์ด๋ค. => ์๋ฅผ ๋ค์ด M, N, x, y ๊ฐ์ด ๋ค ๊ฐ์ ๊ฒฝ์ฐ)
- ๋ง์ฝ i๊ฐ์ N์ผ๋ก ๋๋ด์ ๋, ๋๋จธ์ง๊ฐ (y - 1)์ด๋ผ๋ฉด (x๊ฐ์ -1ํด์คฌ์ผ๋ฏ๋ก y๊ฐ๋ ๋๊ฐ์ด ๋นผ์ค) ์นด์ ๋ฌ๋ ฅ์ผ๋ก ๋ง๋ค ์ ์๋ค๋ ๋ป์ด๋ฏ๋ก ๊ฒฐ๊ณผ๊ฐ์ i๊ฐ์ 1์ ๋ํด์ค ๊ฐ์ ์ ์ฅํ๊ณ ๋ฐ๋ณต๋ฌธ์ ์ข ๋ฃํ๋ค. (x, y๊ฐ์ 1์ ๋นผ์คฌ์ผ๋ฏ๋ก ๊ฒฐ๊ณผ๊ฐ์๋ 1์ ๋ํด์ค๋ค.)
๊ฒช์ ์ํ์ฐฉ์ค
- ์ต๋๊ณต์ฝ์์ ์ต์๊ณต๋ฐฐ์๋ฅผ ํ์ฉํ๋ ๋ฌธ์ ์ธ ๊ฒ์ ๊ณ์ ์ ์ด๋ณด๋ฉด์ ๋ค๋ฆ๊ฒ ๋ฐ๊ฒฌํ๋ค... (์๋นํ ์๊ฐ์ด ๊ฑธ๋ ธ๋ค.. ใ )
- ๊ทธ๋ง์ ๋ ์ฒ์์๋ ์ต์๊ณต๋ฐฐ์๊ฐ ์๋๋ผ ์ต๋๊ณต์ฝ์๋ฅผ ํ์ฉํ๋ ๋ฌธ์ ์ธ์ค ์๊ณ ๊ทธ๋ ๊ฒ ํ๋ค๊ฐ ์์ ๊ฐ ์ ๋ง์ง ์์ ๋ค์ ํ์๋ค... (ใ ใ )
- ๊ทธ๋ ๊ฒ ํผ ์ฝ๋๋ ์ฒ์ ์ ์ถํ์ ๋๋ 'ํ๋ ธ์ต๋๋ค'๊ฐ ๋จ๊ธธ๋ ๋นํฉํ๋ค.
- ์์ ๋ ๋ค ๋ง์๋๋ฐ ์ ํ๋ ธ์งํ๊ณ ๋ฐ๋ก๋ฅผ ์ฐพ์๋ณด๋ M, N, x, y๊ฐ ๋ชจ๋ ๊ฐ์ ์ซ์์ผ ๊ฒฝ์ฐ, ๋ฐ๋ณต๋ฌธ์ ๋ค์ด๊ฐ์ง ๋ชปํด ๋ฌด์กฐ๊ฑด -1์ ์ถ๋ ฅํ๋ค๋ ๊ฒ์ด์๋ค. (์ต์๊ณต๋ฐฐ์์ x, y๊ฐ ๊ฐ์ ๊ฒฝ์ฐ)
- ๊ทธ๋์ ๋ฐ๋ณต๋ฌธ์ ๋ค์ด๊ฐ ์ ์๋๋ก x, y๊ฐ์ -1์ ํด์ฃผ์ด ์์ธ๊ฐ ์๋๋ก ํ๊ณ ๊ฒฐ๊ณผ๊ฐ์ ๊ตฌํ ๋ ๋บ -1์ ๋ค์ ๋ํด์ฃผ๋๋ก ์์ ํ์๋ค.
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ6064 {
static int gcd;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for(int test = 0; test < T; test++){
StringTokenizer st = new StringTokenizer(br.readLine());
// ์ฐ๋ ๊ธฐ์ค
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
// ์นด์ ๋ฌ๋ ฅ์ผ๋ก ๊ตฌํ ํด
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
// ์ต๋๊ณต์ฝ์๋ฅผ ์ ์ฅํ ๋ณ์
gcd = 0;
// ์ต๋๊ณต์ฝ์ ๊ตฌํ๊ธฐ
GCD(M, N);
// ์ต์๊ณต๋ฐฐ์๋ฅผ ์ ์ฅํ ๋ณ์
int lcm = 0;
// ์ต์๊ณต๋ฐฐ์ ๊ตฌํ๊ธฐ
lcm = (M * N)/gcd;
// ๊ฒฐ๊ณผ๊ฐ ์ ์ฅ ๋ณ์
// ํด๋น๋๋ ์นด์ ๋ฌ๋ ฅ ๋
๋๊ฐ ์๋ค๋ฉด -1์ ์ถ๋ ฅํด์ผ๋๋ฏ๋ก
// -1๋ก ์ด๊ธฐํ
int result = -1;
// x๊ฐ์ ๊ธฐ์ค์ผ๋ก ์ต์๊ณต๋ฐฐ์ ์ ๊น์ง ๋ฐ๋ณต
// i๊ฐ์ x๊ฐ์ผ๋ก ์์ํด์ M๊ฐ๋งํผ ๊ณ์ ์ฆ๊ฐ์ํด
// ์ต์๊ณต๋ฐฐ์์ x, y๊ฐ์ด ๋ชจ๋ ๊ฐ์ ๊ฒฝ์ฐ ํด๋น ๋ฐ๋ณต๋ฌธ์
// ์งํํ์ง ๋ชปํ๋ฏ๋ก x, y๊ฐ์ -1์ฒ๋ฆฌํ๊ณ ๋๋ฆผ
for(int i = (x - 1); i < lcm; i = i + M){
// i๊ฐ์ N์ผ๋ก ๋๋ด์๋, ๋๋จธ์ง ๊ฐ์ด y๊ฐ์ผ๋ก ๋์จ๋ค๋ฉด
if(i % N == (y - 1)){
// result๊ฐ์ i๋ก ์ ์ฅํ๊ณ
// ์์์ x, y๊ฐ์ -1์ ํ์ผ๋ฏ๋ก + 1์ ํด์ค
// ๋ฐ๋ณต๋ฌธ ์ข
๋ฃ
result = i + 1;
break;
}
}
sb.append(result + "\n");
}
System.out.println(sb);
}
public static void GCD(int n1, int n2){
// n1์ด n2๋ก ๋๋์ด ๋จ์ด์ง๋ค๋ฉด n2๊ฐ ๋ ์์ ์ต๋๊ณต์ฝ์์ด๋ฏ๋ก
// ์ต๋๊ณต์ฝ์๋ n2๊ณ ํจ์ ์ข
๋ฃ
if(n1 % n2 == 0){
gcd = n2;
return;
}
// ๋ง์ฝ ๋๋์ด๋จ์ด์ง์ง ์๋๋ค๋ฉด ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ์ ์ด์ฉํด์
// n2์ n1์ n2๋ก ๋๋ ๋๋จธ์ง๋ก
// ํจ์๋ฅผ ๋ค์ ๋๋ฆผ
GCD(n2, n1 % n2);
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 11403 ๊ฒฝ๋ก ์ฐพ๊ธฐ (0) | 2024.08.27 |
---|---|
[Java] BOJ 11286 ์ ๋๊ฐ ํ (2) | 2024.08.26 |
[Java] BOJ 5525 IOIOI (0) | 2024.08.24 |
[Java] BOJ 2667 ๋จ์ง๋ฒํธ๋ถ์ด๊ธฐ (0) | 2024.08.23 |
[Java] BOJ 2178 ๋ฏธ๋กํ์ (2) | 2024.08.22 |