[Python] 1082. 방 번호(골3) / 그리디 + DP

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

https://www.acmicpc.net/problem/1082

1082번: 방 번호

---

2. 핵심 아이디어

다른 사람의 풀이를 참고했음에도 사실 이해가 잘 되지 않았다. 

어느정도 이해가 되니 문제는 풀렸지만 이런 사고를 어떻게 떠올리는지는 잘 모르겠다

 

한번 아이디어를 정리해보자

 

가장 큰 숫자라는 건 어떻게 정할 수 있을까?

아마 그리디한 사고로 높은 숫자부터 고려하는 것을 떠올릴 수 있다.

 

그러나, 이 문제가 어려운 점은 여기서 그치지 않고 예산이라는 제한이 들어가기 때문이다.

예산, 그리고 최적의 조합! 무언가 떠오르지 않는가?  맞다. 배낭문제와 비슷하다.

 

그러나, 이 문제는 배낭문제처럼 2차원 dp를 사용하지 않아도 되는데

1차원적으로 각 상황에서 그리디적 사고를 통해 최선의 선택을 해주면 되기 때문이다.

---

그럼 어떤 상황이 있는지 보자

 

상황1) 내가 아무 숫자도 들고 있지 않을 때 => 숫자를 산다

만약 내가 아무 숫자도 들고 있지 않다면 숫자를 무조건 사는 것이 이득이다.

 

상황2) 내가 숫자를 들고 있을 때 => 숫자를 한번 붙여보고 비교한다

내가 숫자를 들고 있다면 우선 숫자를 붙여보고 어떤게 더 큰지 비교할 것이다.

 

이 두 가지 상황을 예시를 통해 살펴보자

번호판	0	1	2
가격	1	2	3

 

 

내가 6원이 있다고 생각해보자

먼저 예산안만큼 dp를 만들어주고 최대값 갱신을 위해 -무한을 설정해준다

 

돈	0	1	2	3	4	5	6
최대숫자	-무한	-무한	-무한	-무한	-무한	-무한	-무한

 

이제 가장 높은 숫자인 2부터 고려하기 시작할 것이다.

2의 가격은 3원이다.

 

 

그럼 2를 살 수 있는 3원부터 고려한다

돈	0	1	2	3	4	5	6
최대숫자	-무한	-무한	-무한	-무한	-무한	-무한	-무한

 

2가지 상황을 고려해보자

상황1) 내가 아무 숫자도 들고 있지 않을 때 => 2를 산다

 

상황2) 내가 숫자를 들고 있을 때 => 2를 한번 붙여보고 비교한다

여기서 2를 붙여보는 행위를 어떻게 할까?

바로 2를 사기 전 상황인 예산이 0원일 때의 숫자(-무한) * 10 +2와 같은 식으로 숫자를 붙여볼 수 있다

 

그럼 dp[3] = max(dp[3], 2(처음 숫자를 산 상황) , dp[3-3]*10 + 2(숫자를 들고 있을 때)) 를 비교할 수 있다

그럼 dp[3]은 최대값인 2가 들어간다

돈	0	1	2	3	4	5	6
최대숫자	-무한	-무한	-무한	2	-무한	-무한	-무한

 

4원, 5원도 같은 상황으로 비교가 가능하다

돈	0	1	2	3	4	5	6
최대숫자	-무한	-무한	-무한	2	2	2	-무한

 

 

이제 예산 6원을 쓸 때의 상황을 보자

상황1. 아무 것도 안샀을 때 => 2

상황2. 숫자를 들고 있을 때 => dp[6-3]*10 +2 (22)

 

이번에는 최대값인 22가 갱신된다

돈	0	1	2	3	4	5	6
최대숫자	-무한	-무한	-무한	2	2	2	22

 

여기까지가 숫자 2에 대한 고려가 모두 끝난 상황이다.

 

같은 방식으로 숫자 1을 고려해보자

숫자 1의 가격은 2원이다, 그렇기 때문에 예산 2원을 쓰는 상황부터 두 상황 중 큰 숫자를 고려해주면 된다

 

예산안 2원 

처음 살 때 => 숫자 1 구매

숫자가 있을 때 => dp[2-2]*10 +1 => -무한 + 1

=> max(1, -무한+1, -무한)

돈	0	1	2	3	4	5	6
최대숫자	-무한	-무한	1	2	2	2	22

 

예산안 3원 

처음 살 때 => 숫자 1 구매

숫자가 있을 때 => dp[3-2]*10 +1 => -무한+1

=> max(1, -무한+1, 2)

돈	0	1	2	3	4	5	6
최대숫자	-무한	-무한	1	2	2	2	22

 

예산안 4원 

처음 살 때 => 숫자 1 구매

숫자가 있을 때 => dp[4-2]*10 +1 => 11

=> max(1, 11, 2)

돈	0	1	2	3	4	5	6
최대숫자	-무한	-무한	1	2	11	2	22

 

예산안 5원 

처음 살 때 => 숫자 1 구매

숫자가 있을 때 => dp[5-2]*10 +1 => 21

=> max(1, 21, 2)

돈	0	1	2	3	4	5	6
최대숫자	-무한	-무한	1	2	11	21	22

 

예산안 6원 

처음 살 때 => 숫자 1 구매

숫자가 있을 때 => dp[6-2]*10 +1 => 111

=> max(1, 111, 22)

돈	0	1	2	3	4	5	6
최대숫자	-무한	-무한	1	2	11	21	111

 

---

이제 나머지 숫자 0도 같은 방식으로 처리해주자

숫자 0의 예산은 1원이다 1원부터 고려해주자

 

예산안 1원 

처음 살 때 => 숫자 0 구매

숫자가 있을 때 => dp[1-1]*10 +0 => -무한 +0

=> max(0, -무한, -무한)

돈	0	1	2	3	4	5	6
최대숫자	-무한	0	1	2	11	21	111

 

 

예산안 2원 

처음 살 때 => 숫자 0 구매

숫자가 있을 때 => dp[2-1]*10 +0 => 00 => 0

=> max(0, 0, 1)

돈	0	1	2	3	4	5	6
최대숫자	-무한	0	1	2	11	21	111

 

 

예산안 3원 

처음 살 때 => 숫자 0 구매

숫자가 있을 때 => dp[3-1]*10 +0 => 10

=> max(0, 10, 2)

돈	0	1	2	3	4	5	6
최대숫자	-무한	-무한	1	10	11	21	111

 

 

예산안 4원 

처음 살 때 => 숫자 0 구매

숫자가 있을 때 => dp[4-1]*10 +0 => 100

=> max(1, 100, 11)

돈	0	1	2	3	4	5	6
최대숫자	-무한	-무한	1	10	100	21	111

 

 

예산안 5원 

처음 살 때 => 숫자 0 구매

숫자가 있을 때 => dp[5-1]*10 +1 => 1000

=> max(0, 1000, 21)

돈	0	1	2	3	4	5	6
최대숫자	-무한	-무한	1	10	100	1000	111

 

예산안 6원 

처음 살 때 => 숫자 0 구매

숫자가 있을 때 => dp[6-1]*10 +1 => 10000

=> max(0, 10000, 111)

돈	0	1	2	3	4	5	6
최대숫자	-무한	-무한	1	10	100	1000	10000

 

 

이렇게 답 10000을 찾아냈다.

 

이제 점화식에 대해 한번 살펴보자

 

예산안이 j일 때 

고려하는 숫자가 num이라고 하고

그 숫자의 가격이 price라고 하고

현재까지의 최대 숫자가 저장된 배열을 dp라고 한다면

점화식은 다음과 같다.

 

dp[j] = max(dp[j], num(처음 산 상황) , dp[j-price] *10 + num(숫자 붙여보기) )

 

 

---

3. 코드

#1082. 방 번호(골3)
import sys


n= int(input())

price = (list(map(int, input().split())))
number = [i for i in range(n)]
money = int(input())
dp=[-sys.maxsize]* (money+1)
result=[]

#뒤에서부터 숫자를 하나씩 고려
for i in range(n-1, -1, -1):
  number_price =  price[i]
  for j in range(number_price, money+1):
    #첫구입이라면 -> 구입하는게 이득 : number[i]
    #두번째 구입이라면 -> price이전의 숫자에서 현재 숫자를 붙인 숫자
    dp[j]= max(dp[j], dp[j-number_price]*10+number[i], number[i])
  #print(dp)
print(dp[money])

---

4.배운점

- 그리디 +DP문제는 항상 그 연관성을 파악하기 힘들게 만든다

- 이 유형은 관련 문제들을 찾아 더 풀어보고 싶다.