문제
https://www.acmicpc.net/problem/12971
문제해설
6개의 양의 정수 X1, X2, X3, P1, P2, P3가 있다.
위 수들은 P1 > X1, P2 > X2, P3 > X3 조건을 만족한다.
N을 P1로 나눈 나머지가 X1, P2로 나눈 나머지가 X2, P3로 나눈 나머지가 X3
위의 조건을 만족하는 가장 작은 N을 구하면 된다.
문제풀이
N이 가능한 범위가 1부터 1,000,000,000까지이다.
그러므로 완전탐색으로는 시간초과가 발생한다.
하지만 잘 생각해보면 1,000,000,000까지 탐색할 필요가 없다.
왜냐하면 사이클이 생기기 때문이다.
예를들어 N이 1이라고 하면 x1, x2, x3가 1이 나올 것이다.
N이 증가하면 x1, x2, x3모두 증가한다.
중간에 다시 0이 될 수도 있지만
적어도 N이 p1 * p2 * p3 에서는 x1, x2, x3가 모두 0이 나온다.
그리고 N이 p1 * p2 * p3 + 1에서 다시 N이 1일 때와 마찬가지로 x1, x2, x3가 1이 나온다.
그러므로 N은 1부터 p1 * p2 * p3까지만 돌며 답을 찾으면 된다.
모든 숫자는 300까지이므로 최대 2천7백만까지만 연산하면 되어 시간초과가 나지 않는다.
전체코드
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int p1, p2, p3, x1, x2, x3;
p1 = Integer.parseInt(st.nextToken());
p2 = Integer.parseInt(st.nextToken());
p3 = Integer.parseInt(st.nextToken());
x1 = Integer.parseInt(st.nextToken());
x2 = Integer.parseInt(st.nextToken());
x3 = Integer.parseInt(st.nextToken());
for (int n = 1; n <= p1 * p2 * p3; n++) {
if (n % p1 == x1 && n % p2 == x2 && n % p3 == x3) {
System.out.println(n);
System.exit(0);
}
}
System.out.println(-1);
br.close();
}
}