[python/파이썬] 백준 1980 햄버거 사랑

[문제 출처]

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

1980번: 햄버거 사랑

 

[문제 풀이]

먹는데 n분 걸리는 버거와 m분 걸리는 버거가 있다. 

t분 안에 햄버거를 먹는데, 햄버거를 먹지 않는 시간에는 콜라를 마시게 된다.

콜라를 마시는 시간을 최소한으로 하면서 최대한 많은 햄버거를 먹는 경우를 구하는 문제이다,

 

 

❌소스 코드1 - 틀렸습니다❌

 

그리디 알고리즘이라고 생각해서 우선 가장 많은 버거를 먹는데 초점을 두었다. 

많은 버거를 먹기 위해선 먹는데 짧은 시간이 걸리는 버거를 많이 먹는 게 유리하다.

따라서 n과 m 중에서 더 작은 값을 구했다.

 

콜라 먹는 시간이 짧은 것이 중요하기 때문에 나눠 떨어지는 경우를 따로 분리하여 체크하였다.

만일 나눠 떨어지지 않는다면 더 오래 걸리는 햄버거를 하나씩 추가하도록 하였다.

 

또한 이렇게 해도 떨어지지 않는다면 전체 시간에서 1씩 감소시키며 같은 과정을 반복하도록 하였다.

 

 

하지만 이 코드에는 문제가 있었는데

3 4 100과 같은 경우

100은 4로 나눠 떨어지기에 25개의 4분짜리 버거를 먹게 되면 콜라를 마시는 시간이 0이 된다.

하지만 조건에는 콜라 마시는 시간이 동일한 경우에는 햄버거를 더 많이 먹는 경우를 답으로 하라고 하였다.

이 경우는 32개의 3분짜리 햄버거와 1개의 4분짜리 햄버거 1개로도 콜라 마시는 시간을 0으로 할 수 있기에 

답은 33 0이 되어야 한다.

 

#1980
n, m, t = list(map(int, input().split()))
time = [n, m]
time.sort()

check = 0
for i in range(t+1):
  T = t - i
  cnt = 0
  while T > 0:
    if T % time[0] == 0:
      cnt += T/time[0]
      check = 1
      break
    elif T % time[1] == 0:
      cnt += T/time[1]
      check = 1
      break
    else:
      T -= time[1]
      cnt += 1
  
  if check == 1:
    break
print("%d %d" %(cnt, i))

 

 

 

⭕소스 코드2 - 맞았습니다!!⭕

 

위의 코드가 채점이 거의 다 됐을 때쯤 틀렸습니다가 떠서 예외를 처리하기 위해서 여러 가지 방법으로 계속해서 시도했으나 

계속해서 틀린 경우가 생겨 접근 방식의 문제가 있다고 판단하여 다른 풀이를 찾아보았는데 아래와 같은 코드가 나왔다.

 

가능한 모든 경우에 대해서 확인해 보는 방식이었다.

t분 동안 먹을 수 있는 n분짜리 햄버거는 최대 t//n 개이고, t분 동안 먹을 수 있는 m분짜리 햄버거는 최대 t//m개 이므로

가장 큰 경우부터 해서 차례로 작아지며 원하는 정답을 찾는 방식으로 코드가 진행된다.

 

그리디 아니라 브루트 포스 알고리즘으로 분류되어 있는 문제이기에

위와 같은 코드는 접근부터가 틀렸고 아래 코드처럼 모든 경우를 따져봐야 한다.

물론 위 코드와 같은 방식으로 정답을 끌어낼 수 있을지도 모르지만 그건 잘 모르겠다.

 

n, m ,t = map(int, input().split())
coke = t
cnt =0
for i in range((t//n),-1,-1):
  for j in range((t//m), -1, -1):
    tmp = n*i + m*j
    if (t-tmp) < coke and (t-tmp) >= 0:
      cnt = i+j
      coke = t - tmp
    elif (t-tmp) == coke:
      if i+j > cnt:
        cnt = i+j
        coke = (t- tmp)
print(cnt,coke)