그리디알고리즘(또 전자레인지야?/S1)

1. 문제

잇창명의 집에는 오래된 전자레인지가 있다. 백준 온라인 저지에서 문제를 너무 많이 푼 잇창명은 문득 이런 궁금증이 생기기 시작했다.

잇창명의 전자레인지에는 다음과 같이 버튼이 4개 있고, 각 버튼을 누르면 다음과 같이 작동한다. 초기 상태에는 조리시간이 0초이고, 조리 중이 아니며, 조리시작 버튼을 눌러야 조리가 시작된다.

• 10초: 조리시간이 10초 늘어난다.
• 1분: 조리시간이 1분(60초) 늘어난다.
• 10분: 조리시간이 10분(600초) 늘어난다.
• 조리시작
  • 조리 중이 아닐 때: 조리가 시작된다. 만약에 조리시간이 0초였다면 30초로 늘어난다.
  • 조리 중일 때: 조리시간이 30초 늘어난다.
• 모든 버튼은 조리 중인지의 여부와 무관하게 항상 누를 수 있으며, 별도의 언급이 없을 경우 항상 같은 동작을 한다.

예를 들어 이 전자레인지로 2분을 맞추려면 조리시작 버튼을 4번 누르면 되지만, 최적의 방법은 아니다. 그 대신 1분-1분-조리시작 순서로 버튼을 누르면 버튼을 누른 횟수가 3번이 되어 최적이다. 1분-1분의 경우에는 조리가 되지 않기 때문에 최적이 아니다. 실제로는 조리 중에는 남은 조리시간이 계속 줄어들고 중간에 조리를 취소할 수 있지만, 이 문제에서는 생각하지 않기로 한다.

잇창명은 지난 한 학기 동안 전자레인지를 이용할 때마다 매번 문제로 내고 싶은 마음이 들어서 괴로워하고 있다. 잇창명을 도와주자!

 

2. 입력

첫 줄에 잇창명이 원하는 조리시간이 M:S 형태로 주어진다(0 ≤ M ≤ 60, 0 ≤ S ≤ 59). M은 분, S는 초이며, 항상 두 자리 숫자로 주어진다.

조리시간은 10초 이상 60분(3600초) 이하이며, 항상 10의 배수이다.

02:00

 

3. 출력

주어진 조리시간을 맞추기 위해 버튼을 눌러야 하는 최소 횟수를 출력한다.

3

 

4. 코드

import sys

m, s = map(int, sys.stdin.readline().strip().split(":"))
result = 1

# 분 계산
if m > 0:
  if m >= 10:
    result += m//10
    m = m - (m//10)*10
  result += m

# 초 계산
if s >= 30:
  result += (s-30)//10
else:
  result += s//10
  
print(result)

 

5. 풀이설명

① 결과값은 마지막 실행 버튼을 생각하여 1로 시작한다.

 

② m(입력받은 분)이 10보다 클경우 10을 나눈 몫에 10을 곱한만큼 결과값에 추가하고 나눈 나머지값도 결과값에 추가한다.

 

③ s(입력받은 초)가 30보다 클경우 s-30을 10으로 나눈 몫을 결과값에 추가한다.

 

④ s(입력받은 초)가 30보다 작을 경우 s를 10으로 나눈 몫을 결과값에 추가한다.

 

⑤ 결과값을 출력한다.

 

6. 느낀점

큰 고민없이 푼 문제로 풀이 ②을 m //10 + m%10 으로 변경하면 더 간략한 코드를 만들 수 있다.