4. 브루트포스 그런데 최소공배수를 곁들인 (백준 6064 파이썬) (백준 1476 파이썬)

실버1인데 6064번 잘 풀려서 쓰는 글 맞습니다. 근데 lcm 함수를 곁들인..

전에 아주 열심히 최대공약수, 최소공배수 구현했었는데, 물론 헛된건 아니지만 함수가 있었음에 꽤나 허무했던 기억이 있어서..^^ 이번에는 최소공배수 함수를 써버렸다..☆

import math 안에

• 최대공약수 : Greatest Common Divisor : math.gcd(A, B)
• 최소공배수 : Least Common Multiple : math.lcd(A, B)

여튼 문제는 아래와 같다.

 

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

6064번: 카잉 달력

문제

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다. 

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다. 

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.  

---

사실 딱 보고 바로 1476번 문제가 생각났었는데, 이 방법대로 했어야 했다.. 이때 내가 푼 방식이 다른 블로그 찾아본 방식이랑 달라서 괜히 그 방법 써보겠다고 했다가 시간 초과 한번 봤다 ^^ㅠ 이 방법대로 했으면 바로 풀렸을 것을..

접근법부터 모르겠다면 1476번 날짜 계산(실버5) 부터 해보길 추천한다..

import sys
import math
sys.stdin = open('6064.txt')

T = int(sys.stdin.readline())

def solution():
    M, N, x, y = map(int, sys.stdin.readline().split())
    last = math.lcm(M, N) # 최소공배수

    while x != y:
        # 최대 연도보다 커지면 불가능 판정
        if x > last or y > last:
            return -1
        
        # 같아질 때까지 최대치씩 증가
        if x < y:
            x += M
        else:
            y += N
    return x

for _ in range(T):
    print(solution())

• 최대 연도를 구하는 데에 최소공배수 함수를 썼음. 구현으로 하면 시간초과 난다는 블로그 글을 보았는데, 함수를 안쓰고 싶다면 M*N을 최대치로 잡아놔도 가능한 것 같다.
• count를 1씩 증가시키는 방법을 쓰면 시간초과가 남

참고로 1476번 풀이는 아래와 같이 했다. (입력이 간단한 문제는 import하기 귀찮아서 숫자 입력으로 함..)

E = 15
S = 28
M = 19

while E != S or S != M:
    temp = min(E, S, M)
    if temp == E:
        E += 15
    elif temp == S:
        S += 28
    elif temp == M:
        M += 19
print(E)

 뿌듯하니까 재밌네 알고리즘..