mminky's

[ 문제 ]

https://softeer.ai/practice/info.do?idx=1&eid=395 

[ 코드 ]

w,n = map(int,input().split())

jewerly = [list(map(int,input().split())) for _ in range(n)]
#금속무게 Mi, Pi가 들어오면 우선 map(int,input().split())으로 각각 정수로 받음
# -> 정수 Mi, Pi를 리스트로 묶음 ex. [Mi, Pi]
# -> [Mi, Pi]리스트를 n개 만듦 (파이썬 2차원 리스트) //https://mminky.tistory.com/141

jewerly.sort(key=lambda x: x[1],reverse=True)
# 리스트 jewerly를 정렬할거임.
# 이때, 기준x의 형태는 x[1]임. 즉, 가격인 Pi를 기준으로 정렬함.
# [Mi, Pi]에서 'Mi의 인덱스는 [0]', 'Pi의 인덱스는 [1]'이기 때문.
# reverse=True를 통해 오름차순 정렬. //https://mminky.tistory.com/170

sum_price = 0
for mi, pi in jewerly: # 리스트 jewerly에 있는 모든 mi,pi에 대해 수행
    # 지금넣는무게 <= 전체가방무게
    if mi <= w :
        sum_price += mi*pi #해당 item을 해당 price만큼
        w -= mi #item넣고 남은 무게로 w 갱신
    # 지금넣는무게 > 전체가방무게
    else:
        sum_price += w*pi #item넣고 남은 무게인 w를 해당 price만큼
        break #남은가방무게 보다 큰 애들이 나오면 끝

print(sum_price)

[ 해결 아이디어 ]

우선 이 문제는 몇 번 틀렸었다.. 그래서 코드별로 정리해보는 아이디어 노트!

1. 리스트 정렬

jewerly.sort(key=lambda x: x[1],reverse=True)

(오답노트)

처음에는 아래 처럼 딕셔너리를 이용해서 정렬을 했다.

# sort_dic_value = list(sort_dic.keys())
# sort_dic_weight = list(sort_dic.values())

하지만 문제는 딕셔너리는 중복이 안 된다.

따라서 [무게, 가치]라고 했을 때, [90, 2] 다음에 [70, 2]가 들어온다면

[90, 2]에 대한 정보는 사라지고 [70, 2]로 갱신되어 버린다.

그래서 값이 틀려진다.

위에 첨부한 코드대로 리스트 정렬을 하자!

2. break 

    # 지금넣는무게 > 전체가방무게
    else:
        sum_price += w*pi #item넣고 남은 무게인 w를 해당 price만큼
        break #남은가방무게 보다 큰 애들이 나오면 끝

(오답노트)

처음에는 else에 break를 쓰지 않았다.

그 결과 테스트케이스를 돌려보니 runtime error가 났다.

for mi, pi in jewerly: 라는 for문을 이용하게 되면 가방 안에 모든 무게를 다 넣어도

jewerly리스트 내의 모든 [mi,pi]에 대해서 반복문을 실행한다.

그래서 가방무게를 초과해서 계산하기도 한다.

어차피 지금 넣는 무게 > 전체 가방 무게 라면 전체가방 만큼만 쪼개어 넣으면 끝이기 때문에

break를 해줘서 for문을 끝내주자!

[ 결과 ]