[파이썬][백준 1082][DP][그리디] 방 번호 - 컴도리돌이

---

1082번: 방 번호

---

풀이 방법

 

처음에는 아무 생각 없이 dfs로 5분만에 풀었다. 하지만 다음 테스트 케이스에서 바로 다이나믹 프로그래밍을 전환.. 

10
1 1 1 1 1 1 1 1 1 1
50

 

1. n의 값만큼 가격 p를 입력 받고, dp의 크기를 입력 받은 m+1 만큼 할당해준다(음의 값으로).

 

2.가격 p를 담고 있는 room의 배열의 마지막 인덱스부터 시작하였다. 마지막 인덱스(방번호)에 해당하는 가격이 x라고 정의할 때, 반복문으로 x 부터 m+1 만큼 dp[현재 요금] = min(dp[현재 요금 - x] * 10 + 현재 방번호(i), 현재 방 번호(i), dp[현재 요금])을 비교를 해준다.

 

다이나믹 + 그리디 문제는 정말 너무 어렵다. 연습해도 좋은 아이디어를 생각하기가 쉽지 않다.ㅠㅠ

---

풀이 코드

import sys ; input = sys.stdin.readline
n = int(input())
room = list(map(int, input().split()))
m = int(input())
dp = [-sys.maxsize] * (m+1)
for i in range(n-1, -1, -1):
    x = room[i]
    for j in range(x, m+1):
      dp[j] = max(dp[j-x]*10+i, i, dp[j])
print(dp[m])