[백준] 1082 - 방 번호

1. 문제

1082번: 방 번호

2. 개요

0 ~ N-1 의 숫자가 있고 각 숫자의 가격, 사용할 수 있는 돈 M이 주어진다.

이때 만들 수 있는 가장 큰 수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

가장 큰 수를 구하는 문제이기 때문에 먼저 수어진 숫자들 중 가장 큰 것부터 넣어본다.

숫자의 가격부터 시작하여 현재 쓴 금액 - 숫자의 가격을 참고하며 dp테이블을 완성시키면 된다.

답이 최대 50자리 수가 나온다.

C#의 경우 ulong으로도 이를 표현할 수가 없어서 string으로 해야하나 했는데

System.Numeric에 BigInteger라는 구조체가 있어서 일단 이를 사용했다.

3-2. Python

import sys

N = int(sys.stdin.readline())

prices = list(map(int, sys.stdin.readline().split()))

M = int(sys.stdin.readline())

dp = [-1 for i in range(M+1)]

for i in range(len(prices)-1, -1, -1):
    for j in range(prices[i], M+1):
        dp[j] = max(dp[j], i, dp[j - prices[i]] * 10 + i)

print(dp[-1])

3-3. C#

using System.Numerics;

namespace boj_1082
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int[] prices = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            int M = int.Parse(Console.ReadLine());

            BigInteger[] dp = new BigInteger[M + 1];
            Array.Fill(dp, -1);

            for (int i = prices.Length - 1; i >= 0; i--)
            {
                for (int j = prices[i]; j < M + 1; j++)
                {
                    dp[j] = BigInteger.Max(BigInteger.Max(dp[j], i), dp[j - prices[i]] * 10 + i);
                }
            }

            Console.WriteLine(dp[M]);
        }
    }
}