[백준 1082번] 방 번호 문제 풀이 (with Python)

< 문제 >

 
 
 
< 입출력 >

 
 
 
 
< 풀이 >
처음 풀때는 구현 + 그리디 문제인줄 알았다. 그래서 방 번호와 가격을 하나의 튜플로 놓고 가격을 기준으로 정렬을 해야겠다고 생각했다. 그 다음 만들 수 있는 가장 긴 자릿수를 구해서, 그 자릿수에서 만들 수 있는 가장 큰 값을 구하는 방식으로 구현했다.
예시 입출력은 동일했으나, 계속 결과값이 틀렸다고 한다. 왜 틀렸는지 모르겠다...
두번째로 인터넷에서 코드를 참고해보았다. 알고보니 DP 문제로 수월하게 풀리는 문제였다.
 DP배열에 해당 돈으로 살 수 있는 방번호의 수 중 가장 큰 값을 저장하면 된다.
 
 
 
 
 
< TRY 1 > - 실패

import sys
input = sys.stdin.readline

price = []
N = int(input())
P = list(map(int, input().split()))
for i in range(N):
    price.append((i, P[i]))
M = int(input())
m = M
result = 0
price.sort(key=lambda x: x[1])

cheapest_number = price[0][0]       # 가장 값이 싼 방 번호
second_number = price[1][0]        # 두번 째로 값이 싼 방 번호

total = 0
while M >= 0:
    if cheapest_number == 0 and total == 0:   # 가장 값이 싼 번호가 0인 경우
        if M >= price[1][1]:
            total = total * 10 + second_number   # 두번 째 값이 싼 번호를 앞 자릿 수로 놓기
            M = M - price[1][1]
        else:
            break
    else:
        if M >= price[0][1]:                  # 가장 값이 싼 번호가 1이 아닌 경우, 최대 길이로 만들 수 있는 숫자 구하기
            total = total * 10 + cheapest_number
            M = M - price[0][1]

        else:
            break

count = len(str(total))  # 최대 자릿수

if count == 1:             # 최대 자릿 수가 1인 경우, 가장 큰 값중 M보다 작거나 같은 값이 결과값
    for i in range(N):
        if P[N-1-i] <= m:
            result = P[N-1-i]
            break

else:
    while count > 0:           # 최대 자릿 수가 1보다 큰 경우, 최소로 필요한 가격을 갱신하면서 최댓값 구하기
        min_required = price[0][1] * (count-1)
        for i in range(N):
            if P[N-1-i] <= m - min_required:
                result += (N-1-i) * 10**(count-1)
                count -= 1
                m = m - P[N-1-i]
                break

print(result)

 
 
< TRY 2 > - 성공

import sys
input = sys.stdin.readline
n = int(input())
room = list(map(int, input().split()))
m = int(input())
dp = [-sys.maxsize for _ in range(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])

 
 

 

 

( + ) < TRY 3 > - 성공 (피드백을 통한 TRY 1 수정)

 

TRY 1의 틀린 부분을 찾지 못해서 포기하려 했으나, 감사하게도 피드백을 받아 고칠 수 있었다...!!😉

 

 

<고려하지 못한 부분>

1. M 보다 작은 가격이 하나밖에 없는 경우 -> 두번째로 작은 가격과 방번호는 첫번째로 작은 가격과 방 번호와 같아야 한 다!! 따라서, price 배열에 넣어 정렬할 때, M보다 작거나 같은 값만 넣어야 하고, len(price)를 통해 M보다 작은 가격이 몇 개 있는지 고려해주어야 한다.

 

2. result 변수는  최종 출력값으로 방번호가 들어가야 한다. 따라서 P배열의 인덱스가 들어가야 하는 것이다.

 

import sys
input = sys.stdin.readline

price = []
N = int(input())
P = list(map(int, input().split()))

M = int(input())
m = M
result = 0

for i in range(N):
    if P[i] <= M: # 맨 처음 넣을때 M 보다 큰 애들은 빼고
        price.append((i, P[i]))

price.sort(key=lambda x: (x[1] , -x[0]))

cheapest_number = price[0][0]  
cheapest_price = price[0][1]

if len(price) > 1:
    second_number = price[1][0]     # M 보다 큰 애들 빼고 넣었을 때
    second_price = price[1][1]      # price 배열의 길이가 1인 경우 ,  1보다 큰 경우 나눠서 처리

else:
    second_number = cheapest_number
    second_price = cheapest_price

total = 0

while M >= 0:
    if cheapest_number == 0 and total == 0:   
        if M >= second_price:
            total = total * 10 + second_number  
            M = M - second_price
        else:
            break
    else:
        if M >= cheapest_price:                  
            total = total * 10 + cheapest_number
            M = M - cheapest_price

        else:
            break

count = len(str(total)) 

if count == 1:             
    for i in range(N):
        if P[N-1-i] <= m:
            result = N-1-i   # result에는 방번호가 들어가야 하므로, P[N-i-1]이 아닌 N-i-1이 들어가야함
            break

else:
    while count > 0:          
        min_required = price[0][1] * (count-1)

        for i in range(N):
            if P[N-1-i] <= m - min_required:
                result += (N-1-i) * 10**(count-1)
                count -= 1
                m = m - P[N-1-i]
                break


print(result)