[백준 / BOJ] 1082 방 번호

문제

출처 : www.acmicpc.net/problem/1082

1082번: 방 번호

갖고있는돈이 주어지고, 각 숫자들의 가격이주어진다 (0~9번까지숫자들의 가격) 이때, 숫자들을 조합해서만들수있는 최댓값을 찾는 문제다.

 

예를들어, 예제 1의경우, 순서대로 

숫자 2를 8원에사고 숫자 1을 7원에 , 숫자 0을 6원에사면, 총 21원으로 210이 만들어지고 이때 최댓값을 갖는다.

 

풀이 

완전탐색으로 풀경우, 최악의 경우, 총 10개의 글자가 중복을 허용해서 50개의 자리에 올수있으므로, 10^50이 나와서 시간초과가 뜬다.

 

dp로 풀어야 하는 문제였다.

1차원 dp로 풀었는데, dp에 저장은

dp[현재 돈] = 현재 돈 으로 만들수있는 최댓값

으로 저장을 해준다.

dp식은

dp[현재돈] = max(dp[현재돈], (1~9) + dp[현재돈 - 1~9까지 숫자들의 가격]) 이 된다.

(이때 0~9가아닌 1~9만 봐주는 이유는, 가장 앞자리에는 0이 올수없기 때문이다.)

 

위 식이 항상 성립하는 이유는

dp테이블에서 항상 최댓값을 저장하며 현재돈을 늘린다 했을때,

가장 앞에 놓일 숫자를 하나 선택하고, 남은돈으로 최댓값을 선택해야하기 때문에, 항상 최댓값을 저장한 dp에서 가져오는것이 성립하는것이다 (돈이 전보다 많아졌을때 만든 숫자의 크기가 전보다 줄어드는 일은 있을수없으니)

 

위처럼 했을때

가장 앞숫자를 선택하고 뒤의 숫자들을 0으로 채울때, 반례가 나온다.

예를들어,

21 과 100을 비교해야하는데, 앞에서 0에대한것을 봐주지않고 넘어갔으므로 21을 선택해버린다.

이를 방지하기 위해, 매 탐색마다 가장 앞 숫자를 선택했을때, 남은돈으로 모두 0을 사는 경우를 추가해서 비교해줬다.

 

최악의 경우 10^50까지 숫자가 늘어나므로 숫자들 저장은 문자열로 해줘야한다. (이거 생각안하고 int로 풀다 틀렸었음)

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1082%20%EB%B0%A9%20%EB%B2%88%ED%98%B8/main.cpp

devxb/JJUNalgo