1082. 방 번호 (Python)

 

1082번: 방 번호

 

풀이

 일단 가장 큰 숫자를 만들기 위해서는 최대한 숫자를 많이 사서 숫자의 길이를 가장 크게 해야한다. 이를 위해 가장 싼 가격을 가진 숫자를 찾아서 M원으로 총 몇 개의 숫자를 살 수 있는지를 체크한다. 이때, 숫자 0은 0 하나일 때를 제외하고 맨 앞에 오지 못하므로 1~N-1 까지의 숫자중 가장 싼 가격의 숫자를 하나 선택하여 제일 앞에 두고 다시 0~N-1 까지의 숫자 중 가장 싼 가격의 숫자를 찾아서 나머지 자리를 채운다.

 

 이렇게 숫자를 만들고나면 M원에서 남은 돈이 있을 수 있다. 이제 이를 통해 맨 앞에서부터 추가로 가격을 지불하여 더 큰 숫자를 만들 수 있는지를 체크해나간다. 이러한 과정을 거치면 가장 큰 방 번호를 구할 수 있다.

 

코드

import sys

if __name__ == '__main__':
    N = int(input())  # 문방구에서 파는 숫자 0 ~ N-1
    price = list(map(int, input().split()))  # 숫자의 가격
    M = int(input())  # 숫자를 구매하기 위해 준비한 금액

    res = [0]  # 방 번호를 저장해 두기 위한 리스트
    minPrice = float('inf')  # 숫자의 가격 중 가장 싼 가격
    minPriceNum = 0  # 가장 싼 가격을 가진 숫자

    for i in range(1, N):  # 0은 맨 앞에 오지 못하므로 처음에는 1부터 체크한다.
        if price[i] <= minPrice:
            minPrice = price[i]
            minPriceNum = i

    # 만약 1부터 N-1까지의 숫자 중 M원으로 살 수 있는 숫자가 없다면 0을 출력하고 종료한다.
    # 문제에서 적어도 하나의 숫자를 살 수 있는 입력만 주어진다고 했으므로 1이상을 사지 못한다면 0은 무조건 살 수 있다.
    if minPrice > M:
        print('0')
        sys.exit(0)

    res[0] = minPriceNum  # res 리스트의 첫 번째 숫자를 설정
    M -= minPrice  # M원에서 minPrice만큼 사용

    if price[0] < minPrice:  # 숫자 0의 가격이 더 쌀 경우 minPrice를 갱신한다.
        minPrice = price[0]
        minPriceNum = 0

    # minPriceNum을 M원으로 살 수 있는 만큼 사서 res 뒤에 붙여준다.
    res += [minPriceNum for _ in range(M // minPrice)]
    remain = M % minPrice  # 이렇게 숫자를 만들고 나서 남은 금액

    # 먼저 첫 번째 숫자에 대해서 남은 금액을 이용하여 더 큰 숫자로 대체할 수 있는지 체크한다.
    if remain != 0:
        for i in range(N-1, res[0], -1):
            if remain >= price[i] - price[res[0]]:
                remain -= (price[i] - price[res[0]])
                res[0] = i
                break

    # 이제 뒤에 숫자에 대해서 남은 금액을 이용하여 더 큰 숫자로 대체할 수 있는지 체크한다.
    for i in range(1, len(res)):
        if remain == 0:
            break

        for j in range(N-1, minPriceNum, -1):
            if remain >= price[j] - minPrice:
                res[i] = j
                remain -= (price[j] - minPrice)
                break

    print(''.join(map(str, res)))