🎀 본 게시물은 Softeer 연습문제 풀이 게시물입니다. 🎀

---

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

이전에 가방문제(냅색 알고리즘) 문제를 풀었기 때문에 비슷한 문제라고 생각했다…

그래서 다음과 같이 풀어보았다.

---

🚀 나의 풀이 ⭕

import sys 
sys.stdin=open("input.txt", 'r')

if __name__=="__main__":
    # input = sys.stdin.readline
    w,n=map(int, input().split())   # 배낭의 무게 W, 귀금속의 종류 개수 N
    arr=[list(map(int, input().split())) for _ in range(n)]
    arr.sort(key=lambda x: x[1], reverse=True)      # 가치가 가장 높은 보석먼저 가방에 때려 넣기 위해 
    
    if w<=arr[0][1]:
        print(arr[0][1]*arr[0][0])
        sys.exit(0)
    else:
        w -= arr[0][1]
        dy=[0]*(w+1)      # index(가방무게)를 채울때 가장 가격이 비싼 경우를 넣는다.
        dy[0]= arr[0][1]*arr[0][0]
        arr[0][1]=0
        T=1
        for i in range(1,n):
            for j in range(T,w+1):
                if arr[i][1]==0:
                    T=j             # 채워 넣었으면 다시 1부터 할필요없잖아
                    break 
                if arr[i][0]+dy[j-1]>dy[j]:
                    dy[j] = arr[i][0]+dy[j-1]
                    arr[i][1]-=1


    print(dy[w])

하지만 시간초가가 뜬다…

냅색 알고리즘에 빠져 다르게 생각못하고 Cut Edge만 생각했다. 결국 못 풀고 다른 블로그를 봤다.

정답

import sys 
sys.stdin=open("input.txt", 'r')

if __name__=="__main__":
    # input = sys.stdin.readline
    w,n=map(int, input().split())   # 배낭의 무게 W, 귀금속의 종류 개수 N
    jewels = [list(map(int, input().split())) for _ in range(n)]
 
    jewels.sort(key=lambda x: x[1], reverse=True)
    
    answer = 0
    for weight, price in jewels:
        if w > weight:
            answer += weight * price
            w -= weight
        else:
            answer += w * price
            break
    
    print(answer)

하… 나는 왜 이렇게 간단하게 생각을 못하는거지?

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기