[백준 BOJ / Python] 27377번 읽씹 멈춰! Greedy (그리디)

문제

문자를 직접 타이핑하는 방법은 s초, 복사&붙여넣기 방법은 t초가 걸릴 때, 같은 말을 n번 반복해서 입력하는데 걸리는 최소 시간을 구하는 문제이다.

풀이

• 같은 말이 c번 적혀있고 추가로 c번 작성한다고 한다면 (2배로 만든다면)
• 위의 그림과 같이 s초씩 c번 작성하는 방법과 t초동안 한 번에 복붙하는 방법이 있다.
• 즉, 최소 시간을 만들기 위해서는 문자를 두배로 만들 때, 두 가지 방법 중 더 적은 시간을 소요하는 방법을 선택해야 한다.

• 같은 말을 n번 작성하는데 걸리는 시간을 계산할 때, 작성된 글 맨 마지막부터 그리디 알고리즘 방식으로 생각하면 쉽다.
• 남은 횟수가 홀수일 경우에는 복붙 방법을 사용할 수 없기 때문에 남은 횟수를 1 줄이고 s초를 더한다.

• 남은 횟수가 짝수일 경우에는 남은 횟수를 절반으로 줄이고, 절반을 복붙하는 방법 t초와 절반을 하나씩 입력한 n*s초를 비교하여 더 작은 시간을 더한다.

• 남은 횟수가 0이 될 때까지 반복하면 최소 시간을 얻을 수 있다.

알고리즘

1. n에 총 반복횟수를 담는다.
2. s,t에 한 번 입력 시간과 복붙 입력 시간을 담는다.
3. 최종 시간을 담을 ans를 생성한다.
4. n을 줄여가며 반복을 할 것임으로 n이 0이상인 동안 while문을 반복한다.
   1. 만약 홀수라면, n을 1 줄이고 ans에 s를 더한다.
   2. 짝수라면, n은 절반으로 줄이고 줄인 n*s와 t 중 더 작은 시간을 더한다.
5. 시간을 출력한다.

Python 코드

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    s,t = map(int, input().split()) 
    ans = 0
    while n > 0:
        if n % 2 == 1:
            n -= 1
            ans += s
        else:
            n //= 2
            ans += min(n*s,t)
    print(ans)

문제 출처

27377번: 읽씹 멈춰!