[백준/ 파이썬] 17828번 문자열 화폐

백준 17828번 문자열 화폐

백준 문자열 화폐문제는 주어진 N자리 문자열을 가지고 주어지는 M을 구하는 문제입니다.
그러면 개별 문자들의 합이 M이 되는 여러 경우가 주어지겠지만 우리는 그중에서 사전순으로 가장 앞서는 문자열을 찾아야 합니다.

아이디어는 주어진 문자열을 가장 최소이자 우선순위가 앞서는 'A'문자로 채워놓습니다.
그다음에는 가장 뒤에서부터 합이 M이 되도록 맞춰 나가면 되는 문제입니다.

1. 모든 문자열을 'A'를 채워놓는다고 가정을 하자.
2. 뒤에서 부터 합이 M이 되도록 맞춰 나가자.

다른 여러가지의 좋은 풀이가 많겠지만 우선 제가 풀이한 방식은
'A'에 대응하는 숫자는 1이기에 N만큼 1을 가지는 리스트를 작성하였고,
우리는 숫자를 통해서 문자를 찾을것이기 때문에 숫자를 key로 가지는 딕셔너리를 생성하였습니다. 그래서 우리는 숫자만 알고있다면 문자는 바로 찾을 수 있습니다.

그리고 제가 첫번째 제출에서는 시간초과로 문제를 틀렸는데
그 이유는 누적합을 계속 처음부터 구해줬기 때문입니다.
그래서 누적합을 구할때는 처음부터 구하는 것이 아니라 처음에 구해놓고 바뀌는 부분만 바꾸어 주었습니다.

그래서 전체코드는 다음과 같습니다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
#1로 리스트를 채워넣었습니다.
arr = [1 for _ in range(n)]

#리스트에 존재하는 숫자에 대응하는 문자를 찾기위해 딕셔너리를 구성하였습니다.
h = {}
for i in range(26):
    h[i+1] = chr(64+i+1)


#처음에만 누적합을 sum을 이용해 구해준다.
total = sum(arr)

for i in range(len(arr)-1, -1, -1):
    if total < m:
        temp = m - total
        if temp >= 26:
            #누적합이 바뀌는 순간
            total -= arr[i]
            arr[i] = 26
            total += arr[i]
        else:
            # 누적합이 바뀌는 순간
            total -= arr[i]
            arr[i] = temp+1
            total += arr[i]
    #이런 경우는 값이 존재하지 않음.
    elif total > m:
        break
    #찾았으면 더이상 바꿀 문자가 없음.
    else:
        break

if total > m:
    print("!")
else:
    if total < m:
        print("!")
    else:
        for el in arr:
            print(h[el], end='')