[Week 2] PACKING self review - ChaeheeKang-GitHub

[chaeheekang]

PACKING self review

1. 해결 시도 과정

BOJ_12865를 푼 후 ans라는 배열을 통해 가져가야하는 물건의 번호를 받도록 설정했습니다.
만일, 0,1,3번의 물건을 가져가야하면 ans 라는 배열에 [0,1,3]이라고 입력이 되어야하는데
코드를 실행시켜보니 [2,4,5]가 배열에 저장되어 원래의 답과 반전(?)되는 결과가 나왔습니다.
이를 해결하고자 ans에 들어 있지 않은 요소를 r_ans배열에 넣으려고 하였고
원하는 정답은 나오지만 시간초과라는 결과가 나오게되었습니다.

2. 작성한 코드와 설명

C=int(input())
for _ in range(C):
    N,W=map(int,input().split())
    name=[]
    volume=[]
    urgency=[]
    ans=[]
    #r_ans=[]
    dp=[[0]*(W+1) for _ in range(N+1)]
    for i in range(N):
        n,v,u=input().split()
        name.append(n)
        volume.append(int(v))
        urgency.append(int(u))
        
    for i in range(1,N+1):
        for j in range(1,W+1):
            if j<volume[i-1]:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-volume[i-1]]+urgency[i-1])
    
    
    for i in range(N):
        capacity=W
        if dp[i][capacity]!=dp[i+1][capacity]:
            capacity-=i
            ans.append(name[i])

    print(dp[N][W],len(ans))
    print(*ans,sep='\n')
    

3. 막힌 점 및 개선 사항

배열이 반전되게 저장되는 문제를 해결할 수 있다면 정답이 도출될 것 같은데 쉽지 않네요..
반복문이 아니라 재귀함수로도 풀어봐야 할 것 같습니다.

[Queue-ri]

알고스팟 PACKING 문제가 파이썬으로 풀기에 좀 타이트한 시간 제한을 가지고 있는데, main 함수를 만들어서 코드를 지역에 넣으시면 비효율성이 많이 해소됩니다.

그리고 현재 이 코드엔 추적하는 로직이 잘못되어있어서 다음과 같이 고쳐봤습니다.

print = sys.stdout.write

def track(dp, volume, name, n, w, cnt):
    if n == 0:
        print(str(cnt) + '\n')
        return
    f = False
    if dp[n][w] != dp[n - 1][w]:
        w -= volume[n - 1]
        cnt += 1
        f = True

    track(dp, volume, name, n - 1, w, cnt)
    if f: print(name[n-1] + '\n')

마지막으로, 중요한 사항은 아니지만 DP 코드 짜실때 인덱스의 시작을 통일해주시면 좋을 것 같습니다.