BOJ-백준 6064번 카잉 달력 Python

BOJ-백준 6064번 카잉 달력 Python 문제 풀이 입니다.

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

6064번: 카잉 달력

✅ Python 정답 코드 입니다. 더보기 클릭!

import sys
from math import gcd
input = sys.stdin.readline

t = int(input())
def cal_year(m,n,x,y):
  last_year=m*n//gcd(m,n)
  year = x
  if m==x and n== y:
    return last_year
  else:
    while year<=last_year:
      if y!=n and year%n == y:
        return year
      elif y==n and year%n == 0:
        return year
      year+=m
    if year>last_year:
      return -1
  return year

result = []
for i in range(t):
  m,n,x,y = map(int, input().split())
  result.append(cal_year(m,n,x,y))
for r in result:
  print(r)

 

📌 해설

 카잉달력의 시초는 <1:1> 로 표기되고, 마지막해를 <M:N>으로 표기 됩니다. <x:y>로 표기되는 해는 몇 번째 해가 되는지 찾는 문제입니다. <10:12>가 마지막 해인 달력이라면 x 자리에는 1~10가 올 수 있고 y자리에는 1~12가 올 수 있습니다. 만약 해당 year을 찾지 못한다면 (마지막 해를 넘길때 까지 못 찾으면) -1을 출력할 수 있도록 합니다. 마지막 해는 x와 y가 공통으로 M과 N으로 돌아온다는 의미이므로 최소 공배수와 같습니다. 

 

🚩 주의

카잉 달력 FAQ 링크 입니다. 주요 반례를 찾는 데에 참고하였습니다. 

https://www.acmicpc.net/board/view/21503

글 읽기 - ★☆★☆★ 필독!!! ★★★ 카잉 달력 FAQ ★★★ 매우중요 ★☆★☆★

FAQ 요약)

- year을 +1 씩 하여 x와 y를 찾으면 시간 초과 입니다. 

- <10:12>인 달력에서 11번째 해는 <1:11> 13번째 해는 <3:1> 입니다. (12번째 해는 <2:12> 입니다.)

- 특수 케이스라고 할 만한 것은 없습니다. ( 코드가 복잡해진다면 해를 구하는 데에 근본적인 오류가 있지 않은지 확인해보아야 합니다. 생각보다 간단한 로직으로 구성된 코드이기 때문입니다.)

 

 

import sys
from math import gcd
input = sys.stdin.readline

1. 필요한 모듈을 불러옵니다.

1-1. 효율적으로 input을 받기 위해 sys.stdin.readline을 사용합니다.

1-2. 최소공배수를 구하기 위해 math 모듈을 사용합니다. 

 

result = []
t = int(input())
for i in range(t):
  m,n,x,y = map(int, input().split())
  result.append(cal_year(m,n,x,y))

2. 필요한 입력을 받습니다.(테스트케이스 갯수 t, 달력 정보 m,n,x,y)

 

def cal_year(m,n,x,y):
  last_year=m*n//gcd(m,n)
  year = x
  if m==x and n== y:
    return last_year
  else:
    while year<=last_year:
      if y!=n and year%n == y:
        return year
      elif y==n and year%n == 0:
        return year
      year+=m
    if year>last_year:
      return -1
  return year

3. year을 계산합니다. 

3-1. m과 n의 최소공약수 gcd를 구하고 m*n//gcd(m,n)을 통해 최소공배수를 구합니다. 

(마지막 해는 x와 y가 1씩 증가하며 m과 n으로 돌아오는 주기이므로 최소공배수와 같습니다.)

3-2. year은 x부터 시작합니다. 

(만약 x ==m, y==n 이라면 while문을 돌지 않고 last_year을 곧 바로 반환합니다.)

3-3. while문을 작성합니다. year이 last_year(마지막 해)를 넘지 않는 동안 진행합니다. 마지막 해를 넘기면 while문이 종료됩니다. 

    3-3.(1) year을 n으로 나눈 나머지가 y 이고, y가 n이 아니라면 year을 반환합니다.

    3-3.(2) year을 n으로 나눈 나머지가 0이고, y가 n이라면 year을 반환합니다.

    3-3.(3) 모두 아니라면 year에 m을 더 합니다. ( 이 과정으로 불필요한 year에 대한 확인 연산을 하지 않아도 해를 구할 수 있게 됩니다. )

 3-4. while문이 종료되고 year이 마지막 해 보다 크다면 해를 구하지 못한것으로 -1을 반환합니다.

 

 

for r in result:
  print(r)

4. result를 출력합니다. 

 

 

::

 

FAQ없었으면 못 풀었을 듯 한 문제,,,

FAQ만들어 주신 분 존경....!