(Week6)[DP] 택배포장

주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요

소요시간: 1시간 +  a

1. 문제 설명

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2063&sca=99&page=18

JUNGOL

박스의 용량이 주어질 때 밀가루를 발송하기 위해 필요한 박스의 최소개수를 구하는 프로그램을 작성하라. 만약, 담을 수 없으면 -1을 return한다. 

2. 접근 방식

 코딩테스트 중 접했던 문제와 비슷한 유형의 문제였다. 당시에는 효율성 문제를 통과하지 못해 비슷한 문제를 찾다 해당 문제를 찾게 되었다. 초기에는 이중 반복문을 사용해 풀었을 때는 시간 복잡도에 걸렸었다. 그래서 DP를 활용해서 풀게 되었다. 

• 각 box_size에 해당하는 인덱스에 1씩 입력
• for문을 돌면서 인덱스 i에서 box_size index 만큼을 빼서 리스트를 만든다.
  [예를 들어 box_size가 3과 5일때, i=6의 경우 [6-3,6-5]의 리스트 생성 가능]
• 이렇게 생성된 리스트를 활용해 dp의 위치를 확인한다.
• 최소로 증가한 값을 해당 위치의 인덱스로 저장
• (예외 케이스) 박스 사이즈가 [3, 5, 33]일 때, 처음에는 3과 5만 고려했었는데 한참 뒤(예를 들어 33)에 도착했을 때, 해당 위치 인덱스를 고려하지 못하는 문제 발생했음. 

3. 코드

# 입력 받기
N = int(input())
box_size = []
for m in range(int(input())):
    box_size.append(int(input()))

# 박스의 용량은 1000까지 / M은 10까지
box_dp = [-1]*(N+1)
for box in box_size:
    box_dp[box] = 1

for idx in range(len(box_dp)):
    min_idx = [idx-box for box in box_size if idx-box>0]
    if min_idx:
        min_ls = [box_dp[num] for num in min_idx if box_dp[num] > 0]
        if min_ls: 
            if -1 < box_dp[idx] < min(min_ls): (이미 인덱스 값이 가장 작으면)
                pass
            else:
                box_dp[idx] = min(min_ls)+1
print(box_dp[N])

4. 코멘트

• dp리스트를 만들 때, -1로 값을 다 채워뒀었는데 min값을 구하는 것이다 보니 별도의 예외처리를 해줘야 했다.
• 따라서 dp를 채울 때, INF(1e9) 정도로 설정해두고, 나중에 이를 -1로 변경해주는 과정을 거치면 좀 더 직관적으로 이해할 수 있을 것 같다.