[softeer] 소프티어(파이썬): 금고털이 ★★

문제

Softeer

- 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 있다.

- 배낭은 1개이며 W kg까지 담을 수 있다.

- 각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 값비싼 가격을 구하는 문제이다.

- 귀금속을 자르면 잘린 부분의 무게만큼 가치를 가진다. 

- 귀금속의 종류가 N일때 1 ≤ N ≤ 10^6 인 정수이다.

- 배낭의 무게가 W일때 1 ≤ W ≤ 10^4 인 정수이다.

- 금속의 무게가 M, 무게당 가격이 P일때 1 ≤ M, P ≤ 10^4 인 정수이다.

알고리즘

- 배낭의 무게와 귀금속의 종류를 입력받는다.

- 금속의 무게와 무게당 가격을 리스트로 입력받아 리스트 변수에 넣는다.

- 계수정렬을 위해 0이 들어간 리스트를 귀금속의 종류만큼 만들어주어 리스트 변수에 넣는다.

- 리스트 변수에 금속의 무게를 무게당 가격의 크기순으로 넣는다.

- 반복문을 통해 배낭의 무게와 리스트의 크기를 비교한다. 이때, 무게당 가격이 큰 것부터 비교하기 위해      revsersed를 통해 리스트를 거꾸로 비교한다.

- 배낭의 무게가 리스트의 크기보다 작으면 배낭의 무게만큼 금속의 무게당 가격을 곱해서 결과값에 더한    다. 여기서 금속을 자르고 자른 부분만 가져가게 되는 것이다.

- 배낭의 무게가 리스트의 크기보다 크다면 금속의 무게와 무게당 가격을 곱해서 결과값에 더한다.

코드

import sys

w, n = map(int, sys.stdin.readline().split())
mp = [list(map(int, sys.stdin.readline().split())) for x in range(n)]
cnt = [0] * (n + 1)

# 리스트 변수에 금속의 무게를 무게당 가격의 크기순으로 넣는다.
for i in range(n):
    cnt[mp[i][1]] += mp[i][0]

result = 0
# 무게당 가격이 큰 것부터 비교하기위해 reversed로 비교한다. 
for i in reversed(range(n + 1)):
    if w < cnt[i]:
        result += w * i
        # 배낭의 무게를 꽉 채웠기때문에 break로 반복문을 빠져나온다.
        break

    result += i * cnt[i]
    # 배낭의 무게를 금속의 무게만큼 빼준다.
    w -= cnt[i]

print(result)

결과

위 코드 밑에 print(cnt)를 작성하면 금속의 무게를 무게당 가격의 크기순으로 만들어 놓은 리스트를 확인할 수 있다.

<출력화면>

위 출력화면을 보게 되면 무게당 가격이 1인 금속은 리스트의 첫 번째 위치해 있고 무게당 가격이 2인 금속은 리스트의 두 번째 위치해 있는 것을 확인할 수 있다.

<출력화면>

위 다른 예시의 출력 화면을 보게 되면 무게당 가격의 값의 크기순으로 금속의 무게가 리스트에 넣어지는 것을 확인할 수 있다. 

따라서 코드를 분석하게 되면 배낭의 무게와 금속의 무게를 무게당 가격의 크기순으로 만들어 놓은 리스트를 비교하고 이때, 배낭의 무게가 더 크면 온전히 금속을 가져갈 수 있기 때문에 금속의 무게와 금속의 가격을 곱한 값을 결과 값에 더하고 반대로 배낭의 무게가 더 작다면 배낭의 무게를 금속의 가격만큼 곱한 값을 결과값에 더하면 되는 것이다. 

github

junjange/CodingTest