[Baekjoon] 6064. 카잉 달력
문제 설명
문제
최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를
예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.
네 개의 정수 M, N, x와 y가 주어질 때,
입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서
출력
출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는
예제 입력 1
3
10 12 3 9
10 12 7 2
13 11 5 6
예제 출력 1
33
-1
83
출처
ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Daejeon Nationalwide Internet Competition 2013 B번
알고리즘 분류
문제 풀이
# Implementation # Math
풀이 과정
이 문제는 입력으로부터 규칙성을 찾아야 하는 문제입니다.
핵심은 x%N 이 y%N을 만족하는 x, y가 있는지 확인하는 것이고, 최대한 효율적으로 답을 구해야 합니다. x에다 M을 더하면 똑같이 x이기 때문에 x에 M을 더해가며 x%N 이 y%N과 같은지 검사하면 됩니다.
x가 M*N보다 커졌는데도 해를 찾지 못 한다면 -1을 출력합니다.
전체 코드
😂 1번 풀이: 시간 초과
for _ in range(int(input())):
M, N, x, y = map(int, input().split())
_x, _y, n = 1, 1, 1
while not (_x==M and _y==N):
_x = n%M if n%M != 0 else M
_y = n%N if n%N != 0 else N
if _x==x and _y==y: break
n += 1
if (_x,_y) == (x,y): print(n)
else: print(-1)
😊 2번 풀이: 정답
for _ in range(int(input())):
M, N, x, y = map(int, input().split())
f = 1
while x <= M*N:
if x%N == y%N:
print(x)
f = 0
break
x += M
if f:
print(-1)
Leave a comment