Menu

Subscribe

[JAVA/백준] SW 역량 테스트 준비-연습 | 브루트 포스: 카잉 달력

HEESOO on Boj

👀 문제

https://www.acmicpc.net/problem/6064

👊 도전

1. 설계

  1. 일반적인 방법으로는 시간 제한이 걸리므로 x를 맞춘 후 y를 확인한다.

2. 구현 (성공 코드)

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

import java.util.Scanner;
/**
 * @author HEESOO
 *
 */
public class Main {
	public static int gcd(int a, int b) {
		if(a%b==0) return b;
		else return gcd(b, a%b);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan=new Scanner(System.in);
		int t=scan.nextInt();
		while(t>0) {
			t--;
			int m=scan.nextInt();
			int n=scan.nextInt();
			int x=scan.nextInt();
			int y=scan.nextInt();
			
			int cnt=x;
			int yy=x;
			int lcm=m*n/gcd(m, n);
			
			for(int i=0;i<n;i++) {
				int ty=yy%n==0? n:yy%n;
				if(ty==y) break;
				yy=ty+m;
				cnt+=m;
			}
			
			if(cnt>lcm) 
				System.out.println("-1");
			else 
				System.out.println(cnt);
		}
	}
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. x를 맞춘 후 y를 생각한다
    • x가 되기 위해 x번이 필요하므로 해를 카운트하는 cnt는 x부터 시작한다.
    • x의 값이 바뀌면 안되기 때문에 값을 m씩 키우며 확인한다. 따라서 yy에 m을 더해야하고, y값은 n이상 넘어가면 안되기 때문에 나머지 연산으로 체크한다.
    • ty를 두어 y와 같아지는 때를 체크한다. ty==y라면 for문을 탈출, 아니라면 yy에 새 값을 갱신해주고 cnt도 갱신한다.
  2. 최소공배수를 이용하여 마지막 해를 넘어가지 않게 한다
    • 문제에서 <10:12>는 마지막 60번째 해라고 설명하였다. 따라서 61번째는 없으므로 cnt가 m, n의 최소공배수를 벗어난다면 유효하지 않은 표현이므로 -1을 출력하도록 한다.

👏 해결 완료!

참고