링크
https://www.acmicpc.net/problem/6064
문제 설명
(정답률 26.448%)
최근에 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>은 카잉 달력의 마지막 해를 나타낸다.
입력 예제
3
10 12 3 9
10 12 7 2
13 11 5 6
출력 예제
33
-1
83
정답 코드
M = 10, N = 12일 때
각각의 해를 구해보면
1번째 : 1, 1
2번째 : 2, 2
...
10번째 : 10, 10
11번째 : 1, 11
12번째 : 2, 12
13번째 : 3, 1
...
23번째 : 3, 11
가 된다.
x를 기준으로 한다면
13번째 x(=3)는 13을 M으로 나눈 나머지
23번째 x(=3)는 23을 M으로 나눈 나머지가 된다.
반대로 n번째를 구한다면 M의 배수에 x를 더한 값이 된다.
23번째는 10*2에 3을 더한 값이다.
그럼 그에 맞는 y를 구한다면
13번째 y는 13을 N으로 나눈 나머지가 되겠지만
x와 y를 각각 구한다면 M과 N의 최대값인 40000일 경우
시간복잡도가 O(MN)으로 1초를 넘어 시간 초과가 나온다.
그래서 x를 기준으로 잡고 구해야 하는데
위에서 구한대로 n번째는 M의 배수에 x를 더한 값이므로
가 되고 이 값이 N의 배수의 y값을 더한 값이 된다.
따라서 이 N으로 나누어 떨어져야 한다.
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int testCase = 0; testCase < t; testCase++) {
int m = sc.nextInt(), n = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt();
int answer = -1;
//for문에 직접 메서드를 넣으면 반복시마다 메서드를 실행시키므로 변수에 할당한다
int lcm = lcm(m, n);
//M의 배수(i*M)는 M과 N의 최대공배수보다 클 수 없다
for (int i = 0; i * m < lcm; i++) {
int temp = i * m + x;
//temp에 y를 뺀 값이 n으로 나누어질 때
if ((temp - y) % n == 0) {
answer = temp;
break;
}
}
System.out.println(answer);
}
}
//유클리드 호제법 최대공약수 메서드
static int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
//유클리드 호제법 최소공배수 메서드
static int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
}정리
다음은 처음에 푼 시간 초과가 난 코드이다.
다른 부분은 동일하고 반복문에서 틀린게 있다.
int answer = 1;
int[] year = {1, 1};
while (!(x == year[0] && y == year[1])) {
if (m > year[0]) {
year[0]++;
} else if (m == year[0]) {
year[0] = 1;
}
if (n > year[1]) {
year[1]++;
} else if (n == year[1]) {
year[1] = 1;
}
answer++;
if (answer > lcm) {
answer = -1;
break;
}
}
System.out.println(answer);문제가 브루트 포스로 분류되어 있길래 단순히
x와 y에 해당하는 크기가 2인 배열을 생성하고
각 원소를 1씩 증가시켜 가며 구했다.
입력 예제로 주어진건 올바른 출력값이 나왔으나
결국 시간초과가 나왔다.
입력값이 40000 39999 40000 39999 이렇게 주어졌을 경우
출력값이 1,599,960,000으로 을 훌쩍 뛰어 넘기 때문이다.
이런 수학적인 센스가 필요한 문제는 볼때마다 너무 어렵다..
