[Baekjoon - 18392] SHOP

난이도: Silver II

 

태그

• Parsing
• Simulation
• Sort

 

풀이

1. 입력에서 원하는 정보를 추출해내는 방법

우선, ','를 기준으로 나눕니다. 이제 각각의 나눠진 문자열을, ':'을 기준으로 나눕니다.

이제 2N개의 정수가 나왔으니, 다 int로 변환해주면 됩니다.

 

2. 시뮬레이션

할 건 별로 없습니다. 문제에서 나온 대로 시뮬레이션하면 되니,

가격 순으로 정렬해서 비싼 것부터 하나씩 줘보면 됩니다.

 

물론 동전을 하나씩 주는 건 오래 걸릴테니, 대신 동전의 종류에 대해 몇 개를 줘야 할 지 계산해야겠죠.

 

3. 코드

for tt in range( int(input()) ):
    print("Customer", tt+1, ":", sep='')
    x = int(input())
    arr = input().strip().split(','); n = len(arr)
    for i in range(n): arr[i] = tuple( map(int, arr[i].split(':')) )
    arr.sort()
    ans = []
    for p in range(n-1, -1, -1):
        c = min(x//arr[p][0], arr[p][1])
        x -= c * arr[p][0]
        if c > 0: ans.append((arr[p][0], c))
    if x > 0: print("Impossible")
    else:
        for p in ans: print(p[0], p[1])