DHistory
[Baekjoon] DP - 1082 방 번호 (오답노트) 본문
문제
1082번: 방 번호
첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다.
www.acmicpc.net
풀이
import sys
n = int(sys.stdin.readline().rstrip())
p = list(map(int, sys.stdin.readline().rstrip().split()))[:n]
m = int(sys.stdin.readline().rstrip())
d = [0] * (m + 1)
# 큰 값을 구해야하므로, 큰 값부터 넣는다.
for i in range(n - 1, -1, -1):
# 숫자의 가격부터 의미가 있으므로 p[i]로 설정한다.
for j in range(p[i], m + 1):
# 현재 숫자의 가격이전의 숫자에서 현재 숫자를 더한다. (0-9 까지이므로 가능)
d[j] = max(d[j], d[j - p[i]] * 10 + i)
print(d[m], sep='\n')
채점 결과
'Computer Science > Algorithm' 카테고리의 다른 글
| [Baekjoon] DFS - 1068 트리 (0) | 2023.11.01 |
|---|---|
| [Baekjoon] Graph - 1043 거짓말 (0) | 2023.11.01 |
| [Baekjoon] Greedy - 1041 주사위 (0) | 2023.11.01 |
| [Baekjoon] Topology Sort - ACM Craft (0) | 2023.10.31 |
| [Baekjoon] Shortest Path - 15723 n단 논법 (0) | 2023.10.31 |