백준 27377: 읽씹 멈춰! (python)

문제

---

풀이

 

(1) 한 글자 타이핑하거나 (2) 지금까지 적은 문자열을 복붙하는 두 가지 연산으로 길이가 n인 문자열을 만드는 최소 비용을 구한다고 생각하면 편하다. n에 따른 DP 배열 계산 pseudocode와 이를 기반으로 한 코드를 대충 적어 보면 다음과 같다.

dp[1] = s	# 처음은 무조건 한 글자 타이핑하고 시작
if n == 짝수: dp[n] = min(dp[n//2] + t, dp[n-1] + s)	# n이 짝수라면 n//2에서 복붙해서 오거나 n-1에서 한 글자 타이핑해서 올 수 있음
elif n == 홀수: dp[n] = dp[n-1] + s	# n이 홀수라면 복붙해서 올 수 없음

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    s, t = map(int, input().split())    # s: 타이핑 시간 / t: 복붙 시간

    dp = [0 for i in range(n + 1)]
    dp[0] = 0
    dp[1] = s

    if n > 1:
        for i in range(2, n + 1):
            if i % 2 == 0:
                dp[i] = min(dp[i // 2] + t, dp[i - 1] + s)
            else:
                dp[i] = dp[i - 1] + s
    print(dp[n])

간단하게 생각하면 골자는 이런데, 문제는 이렇게 제출하면 메모리 초과로 틀린다. n이 10**18까지이므로 n까지 dp배열을 모두 만드는 건 당연히 불가능하기 때문... 처음에는 dp로도 풀리는 문제 아닌가 싶었는데, 알고리즘 분류에 dp가 아니라 그리디만 있는 이유가 이것인 듯 하다. 그래서 n까지 전체 수에 대해 dp 배열을 만들지 말고 n부터 1까지 역순으로 진행하면서 각 dp[i] 단계별로 i가 짝수인지 홀수인지에 따라 계산하는 아이디어가 중요하다.

res = 0
while n > 1:
    if n % 2 == 0:  # 짝수라면
        res += min(t, s * (n // 2)) # n//2에서 복붙 t vs n-1에서 타이핑 s
        n //= 2
    else:           # 홀수라면
        res += s
        n -= 1
res += s  # 마지막 1개는 직접 타이핑

n의 홀짝 여부에 따라 케이스 나누는 것은 동일. while문으로 n → 1 역순 진행하며 복붙과 타이핑 중 유리한 것을 선택, 선택할 때마다 res에 s 또는 t를 더하고 n 인덱스를 변경한다.

 

전체 코드

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    s, t = map(int, input().split())

    res = 0
    while n > 1:
        if n % 2 == 0:  # 짝수라면
            res += min(t, s * (n // 2)) # n//2에서 복붙 t vs n-1에서 타이핑 s
            n //= 2
        else:           # 홀수라면
            res += s
            n -= 1
    res += s  # 마지막 1개는 직접 타이핑
    print(res)

좀 느린가 싶긴 한데 풀린다