[Python] 백준 1082번: 방 번호

https://www.acmicpc.net/problem/1082

 

import sys
input = sys.stdin.readline


def getNumbersWithMaxDigit():
    global money

    numbersWithMaxDigit = []

    # 0 제외한 숫자들 중에 가장 싼 것으로 첫자리 결정
    minCost, minIndex = getMinCostAndIndex(costs[1:10])
    if money - minCost < 0:
        return []

    money -= minCost
    numbersWithMaxDigit.append(minIndex+1)

    # 가장 싼 것으로 남은 자리들 결정
    minCost, minIndex = getMinCostAndIndex(costs)
    while money-minCost >= 0:
        money -= minCost
        numbersWithMaxDigit.append(minIndex)

    return numbersWithMaxDigit


def getMinCostAndIndex(costs):
    minCost = costs[0]
    minIndex = 0

    for i in range(1, len(costs)):
        if minCost > costs[i]:
            minCost = costs[i]
            minIndex = i

    return minCost, minIndex


# curNums를 앞자리부터, 최대한 큰 숫자로 교체
def getPossibleMaxNumber(nums):
    global money

    for i in range(maxDigit):
        possibleMaxDigit = getPossibleMaxDigit(nums, i)

        if possibleMaxDigit != -1:
            money += costs[nums[i]] - costs[possibleMaxDigit]
            nums[i] = possibleMaxDigit

    return nums


# nums[index]에서 변경할 수 있는 가장 큰 숫자를 반환함
def getPossibleMaxDigit(nums, index):
    target = nums[index]

    for i in range(N-1, target, -1):
        if money + costs[target] - costs[i] >= 0:
            return i

    return -1


N = int(input())
costs = list(map(int, input().split()))
money = int(input())

if N == 1:
    print(0)
else:
    # 자릿수 지정
    numbersWithMaxDigit = getNumbersWithMaxDigit()
    maxDigit = len(numbersWithMaxDigit)

    # 주어진 돈으로 0이상의 값이 나오지 않음
    if maxDigit == 0:
        print(0)
    else:
        # 연산
        numbersWithMaxDigit = getPossibleMaxNumber(numbersWithMaxDigit)

        # 출력
        for n in numbersWithMaxDigit:
            print(n, end="")

 

우선 자릿수를 높이는 것이, 숫자를 크게 하는 것에 있어서 우선순위가 가장 높으므로 최우선시 되어야한다. 따라서 먼저 자릿수부터 지정을 한다. 주어진 가격을 기반으로 가장 싼 숫자를 찾고, 그 숫자로 모든 자릿수를 채운다. 단, 첫째자리는 0이 올 수 없으므로 이것을 유의해야한다. 가령 예제 입력 1이 입력되었다면, 100이 될 것이다.

다음으로, 이렇게 정해진 자릿수를 유지해가면서 최대한 큰 숫자가 나오게끔 해야한다. 이것을 위해 앞자리부터 탐색하면서, 남은 돈으로 살 수 있는 가장 큰 숫자를 구입하면 된다.

마지막으로, 출력을 해주면 끝이다.

 

예외 처리해야할 부분은 총 2개의 경우가 있다.

첫번째로 N이 1인 경우인데, 0만 구입할 수 있으므로 정답은 무조건 0이다.

다음은 getNumbersWithMaxDigit()를 통해 얻은 리스트의 길이가 0인 경우이다. 해당 함수가 빈 배열을 반환했다는 것은, 첫째자리를 정해줄 때, 0을 제외하고 구입할 수 있는 것이 없었다는 것을 의미한다.