[Java] 백준(실버-1) 6064번 - 카잉 달력
문제 풀이
이번 문제는 문제의 요구사항을 통해 두 수의 관계를 고려하여 나머지 연산을 활용해 풀어야 한다.
아이디어 도출
문제 요구사항을 다시 살펴보자.
만일 x < M 이면 x’ = x + 1이고, 그렇지 않으면 x’ = 1이다. 같은 방식으로 만일 y < N이면 y’ = y + 1이고, 그렇지 않으면 y’ = 1이다.
그렇다면 예를 들어보자.
1
2
3
4
5
6
7
8
// <M, N>이 <10, 12>일 때
1번째 해 : <1, 1>
2번째 해 : <2, 2>
...
10번째 해 : <10, 10>
11번째 해 : <1, 11>
12번째 해 : <2, 12>
13번째 해 : <3, 1>
위처럼 x가 M, y가 N에 도달하는 순간 1로 변경된다.
여기서 완전탐색을 통해 하나씩 모두 계산할 경우 O(nm)의 시간복잡도를 가지기에 시간초과가 발생할 수 있다.
문제를 풀기 위한 아이디어는 바로 나머지 연산에 있다.
1
2
3
4
5
6
7
8
// <10, 12>
1번째 해 : <1, 1>
2번째 해 : <2, 2>
3번째 해 : <3, 3>
...
13번째 해 : <3, 1>
...
23번째 해 : <3, 11>
3, 13, 23번째를 보면 M의 배수에서 3만큼 더한 값을 넘어야 3이 나오게 된다. 시간초과를 고려해 모든 경우를 다 구하며 계산할 순 없기 때문에, x값을 기준으로 y값을 함께 N으로 나눈 나머지가 y가 나오는지 확인하면 된다.
결국, 구할 수 있는 최대 범위는 M과 N의 최소공배수인데 이를 초과하는 경우는 표현될 수 있는 해가 없다는 것이기에 -1로 만들면 된다.
문제 풀이를 위한 아이디어는 다음과 같다.
- M과 N의 최소공배수를 구하여 최소공배수까지 순회한다.
- 순회하며 x값을 기준으로 y값도 N으로 나눈 나머지가 y가 된다면 해를 출력한다.
- 순회하며 2번 기준이 충족되지 않는다면 구할 수 없는 해이기에 -1을 출력한다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
int T = Integer.parseInt(br.readLine());
while(T --> 0) {
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());
// 최소 공배수 구해오기
int lcm = LCM(M, N);
// while 조건을 충족하지 않아 구할 수 없는 해라면 -1을 출력하기 위해 -1로 초기화한다.
int result = -1;
// 최소공배수의 범위를 벗어나면 구할 수 없는 해이다.
// x값과 y값을 N으로 나눈 나머지가 y인지 확인하여 해를 구한다.
int cnt = 0;
while((cnt * M) < lcm) {
if(((cnt * M) + x - y) % N == 0) {
result = (cnt * M) + x;
break;
}
cnt++;
}
bw.write(result+"\n");
}
}
}
// 최소 공배수
public static int LCM(int x, int y) {
return x * y / GCD(x, y);
}
// 최대 공약수
public static int GCD(int x, int y) {
while(y != 0) {
int r = x % y;
x = y;
y = r;
}
return x;
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.