[Algorithm/Java] 백준 6064번 - 카잉 달력
https://www.acmicpc.net/problem/6064
📌 문제
문제 유형
- 수학
- 브루트포스
- 정수론
- 중국인의 나머지 정리
문제 설명
입력
3
10 12 3 9
10 12 7 2
13 11 5 6
출력
33
-1
83
🔍 문제 풀이
① 최소공배수 범위 안에서 해를 탐색
M과 N의 최소공배수까지는 모든 경우가 순환되므로, k는 최대 lcm(M, N)까지만 보면 된다.
- 최소공배수(LCM)는 x와 y의 패턴이 동시에 처음으로 돌아오는 시점이다.
- 이 시점까지는
- LCM 이상까지는 볼 필요가 없다.
예시: M=5, N=7
1: <1,1> 6: <1,6> 11<1,4> 16<1,2> 21<1,7> 26<1,5> 31<1,3>
2: <2,2> 7: <2,7> 12<2,5> 17<2,3> 22<2,1> 27<2,6> 32<2,4>
3: <3,3> 8: <3,1> 13<3,6> 18<3,4> 23<3,2> 28<3,7> 33<3,5>
4: <4,4> 9: <4,2> 14<4,7> 19<4,5> 24<4,3> 29<4,1> 34<4,6>
5: <5,5> 10:<5,3> 15<5,1> 20<5,6> 25<5,4> 30<5,2> 35<5,7>
- 36년부터는 1년 차랑 똑같아짐
- 즉, 36년부터는 1~35년 내용을 다시 복사해서 반복하는 것과 같음 (x는 5년마다 한 바퀴, y는 7년마다 한 바퀴)
- 둘 다 동시에 처음 상태로 돌아오려면 5와 7의 공통 반복 지점이 필요함 -> 최소공배수 = 35년
- 정리하자면,
- M년, N년 주기로 반복되는 달력이므로
- 두 주기가 동시에 다시 시작되는 해 = 최소공배수(LCM(M, N))
- 그 이후는 똑같이 반복되므로 LCM까지만 보면 충분
② x부터 시작해서 k += M씩 증가시키며 (k % N == y)인지 확인
for (int k = x; k < lcm; k += m)
찾는 해 k는 아래 조건을 만족해야한다.
k ≡ x (mod M) → k % M == x
k ≡ y (mod N) → k % N == y
그런데 x부터 시작해서 k += M씩 가면 k % M == x는 항상 만족한다.
예시: M = 5, N = 7, x = 2, y = 1
k ≡ 2 mod 5 -> k = 2, 7, 12, 17, 22, 27, 32
이 중에서 k % 7 == 1이 되는지 확인
2 % 7 = 2 -> x
7 % 7 = 0 -> x
12 % 7 = 5 -> x
17 % 7 = 3 -> x
22 % 7 = 1 -> o
정답: k = 22
따라서, x부터 시작해서 m씩 증가시키면 항상 k % m == x를 만족하는 해만 보게 된다.
③ 이제 k % N == y만 맞는지 확인하면 된다.
- x 조건은 이미 만족된 상태니까 y만 확인하기
k = x부터k += M씩 가면서k % N == y만 보면 됨- 만족하면 그
k가 정답 - 없으면 끝까지 돌고
-1출력
예시: 10 12 3 9
- M = 10, N = 12, x = 3, y = 9
- x, y를 0부터 시작하게
x = 2,y = 8로 조정 -
최소공배수 LCM(10, 12) = 60
k % 10 == 2를 만족하는 해들: 2, 12, 22, 32, 42, 52- 이 중
k % 12 == 8인 해는? 32
해는 0부터 세니까 32 + 1 = 33
정답: 33
📌 놓친 점
k를 1부터 전부 검사하면 시간 초과
처음에는 단순하게 1부터 k를 늘려가며
(k - 1) % M + 1 == x 와 (k - 1) % N + 1 == y를 매번 검사했다.
하지만, 시간초과가 발생하여 x부터 시작해서 m씩 증가시키는 방식으로 개선하여 문제를 해결하였다.
달력 값은 1부터 시작하지만
%연산 결과는 0부터 시작함 (0-based)
x와 y는 문제에서 1부터 시작하지만,
Java의 % 연산은 결과가 0부터 나오므로 그대로 비교하면 맞지 않을 수 있다.
그래서 x와 y를 입력받을 때 1을 빼서 0부터 시작하도록 바꿔준 뒤,
k % M == x, k % N == y로 비교하였다.
이를 숫자로 1부터 센다고 하여 1-based라고 한다.
- 두 가지 방법
- 1-based:
(k - 1) % m + 1 - 0-based:
k % m→ (주의) 입력에서-1하고, 출력할때+1필수
- 1-based:
%를 하는 이유
x는 m년 주기 y는 n년 주기로 반복된다.
curX = k % m;- k년 차에서의 x값 계산
- x는 m년마다 반복되니까
% m사용
curY = k % n;- k년 차에서의 y값 계산
- y는 n년마다 반복되니까
% n사용
따라서 %를 사용하면, 주기 안 현재 위치를 구할 수 있다.
💻 전체 코드
개선된 브루투포스 방식
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
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()) - 1;
int y = Integer.parseInt(st.nextToken()) - 1;
int gcd = getGCD(m, n);
int lcm = m * n / gcd; // 최소공배수
int result = -1;
for(int k=x; k < lcm; k += m){
int curX = k % m;
int curY = k % n;
if(curX == x && curY == y){
result = k + 1;
break;
}
}
System.out.println(result);
}
}
public static int getGCD(int m, int n){
if(n == 0) return m;
return getGCD(n, m%n);
}
}
브루트포스 방식 (시간초과)
simport java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
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()) - 1;
int y = Integer.parseInt(st.nextToken()) - 1;
int gcd = getGCD(m, n);
int lcm = m * n / gcd; // 최소 공배수
int result = -1; // 해가 없을 경우
// 1부터 lcm까지 전부 확인 (비효율적)
for (int k = 1; k <= lcm; k++) {
int currX = k % m;
int currY = k % n;
if (currX == x && currY == y) {
result = k + 1;
break;
}
}
sb.append(result).append("\n");
}
System.out.print(sb);
}
private static int getGCD(int m, int n) {
if(n == 0) return m;
return getGCD(n, m % n);
}
}
댓글남기기