[그리디] 코딩테스트 문제 TIL (전자레인지) - 백준 10162번

말하는 감자·2024년 12월 23일

TIL algorithm baekjoon greedy python 그리디 백준 알고리즘 코딩테스트 코딩테스트 준비 파이썬

코딩테스트 유형별 풀이

목록 보기

43/67

오늘 문제는 그리디 알고리즘의 제일 기본 문제입니다.

1. 오늘의 학습 키워드

그리디 알고리즘

2. 문제: 10162. 전자레인지

단계: 🥉 브론즈 3단계
주제:
출처: https://www.acmicpc.net/problem/10162

문제

3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 각각 5분, 1분, 10초이다.

냉동음식마다 전자레인지로 요리해야할 시간 T가 초단위로 표시되어 있다. 우리는 A, B, C 3개의 버튼을 적절히 눌러서 그 시간의 합이 정확히 T초가 되도록 해야 한다. 단 버튼 A, B, C를 누른 횟수의 합은 항상 최소가 되어야 한다. 이것을 최소버튼 조작이라고 한다.

만일 요리시간이 100초라고 하면(T=100) B를 1번, C는 4번 누르면 된다. 이와 다르게 C를 10번 눌러도 100초가 되지만 이 경우 10번은 최소 횟수가 아니기 때문이 답이 될 수 없다. 이 경우 B 1번, C 4번, 총 5번이 최소버튼 조작이다. 그리고 T=234와 같이 3개의 버튼으로 시간을 정확히 맞출 수 없는 경우도 있다.

여러분은 주어진 요리시간 T초를 맞추기 위한 최소버튼 조작 방법을 구하는 프로그램을 작성해야 한다.

입력

첫 번째 줄에는 요리시간 T(초)가 정수로 주어져 있으며 그 범위는 1 ≤ T ≤ 10,000 이다.

출력

여러분은 T초를 위한 최소버튼 조작의 A B C 횟수를 첫 줄에 차례대로 출력해야 한다. 각각의 횟수 사이에는 빈 칸을 둔다. 해당 버튼을 누르지 않는 경우에는 숫자 0을 출력해야한다. 만일 제시된 3개의 버튼으로 T초를 맞출 수 없으면 음수 -1을 첫 줄에 출력해야 한다.

서브태스크

번호	배점	제한
1	30	T ≤ 60
2	30	T ≤ 300
3	40	T ≤ 10,000

예제 입력 1 복사

예제 출력 1 복사

0 1 4

예제 입력 2 복사

예제 출력 2 복사

-1

3. 문제 풀이

Step1. 문제 이해하기 및 문제 분석하기

오늘 문제는 흔히 아는 거스름돈 문제라고 생각하시면 편합니다.

요리시간 T가 주어질 때 버튼 A, B, C을 조작해서 주어진 시간 T에 맞춰야합니다. 그럴 때 최소버튼 조작 횟수를 각 버튼별로 출력을 하는 문제입니다.

A버튼은 5분, B버튼은 1분, C버튼은 10초로 나머지 버튼 B, C가 가장 시간이 오래걸리는 A버튼의 약수인 것을 알 수 있습니다.

따라서, 가장 오래 걸리는 A버튼부터 조작 횟수를 파악하면 최소 횟수를 구할 수 있는 전형적인 그리디 알고리즘 문제입니다.

T는 1이상 $10^4$ 이하이며, 버튼의 개수는 3개입니다. 따라서, 시간 복잡도상으로 충분히 여유가 있습니다.

바로 코드 구현을 진행하도록 하겠습니다.

Step2. 코드 구현

import sys
T = int(sys.stdin.readline().strip())
def sol(T):
    if T % 10 != 0:
        return -1
    result = []
    # A, B, C = [300, 60, 10]
    for t in [300, 60, 10]:
        result.append(T // t)
        T %= t
    return ' '.join(map(str, result))
print(sol(T=T))

코드 분석

입력 처리
```
T = int(sys.stdin.readline().strip())
```
- 시간 복잡도: O(1)
- 입력을 한 번 읽고 정수로 변환하는 작업이므로 상수 시간 입니다.
함수 sol(T)
```
if T % 10 != 0:
    return -1
```
- T%10 연산은 상수 시간 O(1).
```
for t in [300, 60, 10]:
    result.append(T // t)
    T %= t
```
- for 루프는 고정된 3개의 요소 ([300, 60, 10])를 순회합니다.
- 각 루프에서 실행되는 연산:
  - T // t 및 T %= t: 둘 다 나눗셈 및 나머지 연산으로, 상수 시간 O(1).
  - result.append(): 리스트에 값을 추가하는 작업으로 상수 시간 .
- 루프는 항상 3번 실행되므로 전체 시간 복잡도는 O(3), 즉 O(1).
출력 처리
```
return ' '.join(map(str, result))
```
- map은 리스트의 길이와 비례하는 작업이지만, 리스트 result의 길이는 항상 3이므로 O(1).
- ' '.join(...)은 문자열 연결 작업으로, 리스트의 총 문자열 길이에 비례하지만 리스트 길이가 3으로 고정되어 있으므로 O(1).