백준 6064 - 카잉 달력 (파이썬)

 

풀이

이 문제는 브루트포스 방법을 이용해 특정 해가 몇 번쨰 해인지 구하는 문제이다.

단순히 모든 연도를 하나씩 증가시키며 탐색하면 시간 복잡도가 O(M * N)으로 너무 커지기 때문에 시간 초과가 일어 날 수 있다.

found = False
first = y

• found = False: x:y에 해당하는 해를 찾았는지 여부를 저장하는 변수
• first = y: y를 기준으로 탐색을 시작

for i in range(M):
    if first == x:
        print(y + i * N)
        found = True
        break

• first 값을 N씩 증가시키면서 x와 같은 값을 찾기
• 만약 first == x가 되는 순간, 해당 연도가 답이므로 출력 후 종료

first += N
if first > N:
    first -= M

• first를 N만큼 증가시키면서 다음 가능한 연도를 탐색
• first가 N을 초과하면, M을 빼면서 조정

정리하면

• (M, N)을 정렬하여 큰 값을 기준으로 탐색
  • 탐색 범위를 줄이기 위한 최적화.
• y부터 시작하여 N씩 증가시키면서 x를 찾음
  • first += N 방식으로 x와 일치하는 해를 찾기
• 찾지 못하면 1 출력
  • 가능한 연도가 없으면 1을 반환.

하지만 이렇게 하면 틀림

if M < N :
  M, N = N, M
  x, y = y, x

M < N 일때 M, N 을 교체하는데, 주어진 순서 그대로 계산 되어야함.

found = False
first = y
for i in range(M):
    if first == x:
        print(y + i * N)
        found = True
        break

    first += N
    if first > N:
        first -= M

• first += N을 반복하면서 x를 찾고 있지만, 이 방식은 올바른 연도를 찾는 방식이 아님.
• 실제로 문제를 해결하려면 x를 기준으로 M씩 증가하면서 y를 찾는 방식이어야 합니다.

코드

# 백준 6064 - 카잉 달력
# 분류 : 브루트포스

import sys
input = sys.stdin.read
data = input().splitlines()

T = int(data[0])
result = []

for i in range(1, T + 1):
    M, N, x, y = map(int, data[i].split())

    k = x  # x에서 시작
    found = False

    while k <= M * N:
        if (k - y) % N == 0:
            result.append(str(k))
            found = True
            break
        k += M

    if not found:
        result.append("-1")

sys.stdout.write("\n".join(result) + "\n")