[백준] 상근타워 #3541

기억할 것 

n이 엄청 크다 (1000000 그이상 ) -> 시간 초과 날 가능성이 있다

문제

상근이는 남는 돈으로 매우 높은 빌딩 "상근타워"를 지었다.

상근타워에는 엘리베이터가 m개가 있다. 각 엘리베이터에는 두 버튼이 있다. i번째 엘리베이터의 한 버튼은 ui 층을 올라가는 버튼이고, 다른 버튼은 di층 내려가는 버튼이다.

상근타워의 가장 아래층(로비)은 0층이고, 그 다음 층부터는 증가하는 자연수이다. 엘리베이터를 타고 지하로 내려갈 수 없으며, 건물은 매우 높아 끝이 없다고 가정한다.

상근이는 상근타워의 로비에 서있다. 이제, 엘리베이터중 하나를 골라서 타려고 한다. 엘리베이터를 탄 이후에는 다른 엘리베이터로 바꿔탈 수 없다. 이때, 엘리베이터 버튼을 정확하게 n번 눌러서 갈 수 있는 가장 낮은 층(로비는 제외)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n과 m이 주어진다. (1 ≤ n ≤ 1,000,000, 1 ≤ m ≤ 2,000) 다음 m개 줄에는 각 엘리베이터의 버튼 ui와 di가 주어진다. (1 ≤ ui, di ≤ 1000)

출력

엘리베이터를 타고 버튼을 n번 눌러서 갈 수 있는 가장 낮은 층을 출력한다.

예제 입력 1 복사

10 3
15 12
15 4
7 12

예제 출력 1 복사

13

 

 

처음엔 아 그냥 구현만 하면 되지 하고 암생각없이 풀어서 시간초과 남,, 계속 계산되는 부분은 최소공배수 개념을 이용하여 쳐내는 게 필요. 

 

오답 코드

import sys
n, m = map(int, sys.stdin.readline().split())
elevators = []
for i in range(m):
    a,b = map(int, sys.stdin.readline().split())
    elevators.append((a,b))


tmp = []

for elevator in elevators:
    current = 0
    for j in range(n):
        if current > elevator[1] : 
            current -= elevator[1]
        else :
            current += elevator[0]

    tmp.append(current)
print(min(tmp))

 

정답 코드

import sys
import math 
n, m = map(int, sys.stdin.readline().split())
elevators = []
for i in range(m):
    a,b = map(int, sys.stdin.readline().split())
    elevators.append((a,b))


tmp = []

for elevator in elevators:
    current = 0
    lcm = math.lcm(elevator[0], elevator[1])
    k =( n % (lcm //elevator[0] + lcm //elevator[1])) + lcm //elevator[0] + lcm //elevator[1]

    for j in range(k):
        if current > elevator[1] : 
            current -= elevator[1]
        else :
            current += elevator[0]

    tmp.append(current)

print(min(tmp))