[백준] 1106 - 호텔

1. 문제

1106번: 호텔

2. 개요

호텔의 수입을 늘리기위해 도시에서 홍보를 하려고 한다.

도시별로 홍보에 드는 비용과 홍보 시 얻을 수 있는 고객의 수가 주어진다.

이 때, 각 비용의 정수 배 만큼 투자하여 같은 비율만큼 고객을 더 얻을 수 있다.

각 도시에 무한한 잠재 고객이 있다고 할 때, 최소 C명의 추가 고객을 얻기 위한 최소 투자 비용을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

배낭문제이다.

투자 비용의 최대값은 100000으로 각 도시별로 100000 만큼 dp테이블을 만들어둔다.

해당 인덱스의 값은 해당 인덱스의 투자를 했을 때 얻을 수 있는 고객의 최댓값을 나타낼것이다.

각 도시의 정보마다 0원부터 시작하여 dp테이블을 채워나간다.

현 도시의 홍보 최소비용보다 작다면 전 도시의 해당 액수 투자시의 고객을 끌어온다.

홍보 최소비용 이상이라면, 전 도시의 해당 액수 투자시의 고객,

전 도시의 (해당 액수 - 현 도시의 최소 비용) 투자시의 고객 + 현 도시의 최소비용 투자시의 고객,

현 도시의 (현재 액수 - 최소 투자비용) 투자시의 고객 + 최소비용 투자시의 고객 세 값을 비교하여 가장 큰 값으로 갱신한다.

만약 이 값이 C이상이라면 j를 답과 비교하여 더 작은 값으로 갱신하고 다음 도시로 넘어간다.

모든 도시 정보에 대한 탐색이 끝났다면 답을 출력한다.

3-2. Python

import sys

C, N = map(int, sys.stdin.readline().split())
dp = [[0 for j in range(100001)] for i in range(N+1)]
cities = [[0, 0]]
ans = 100001

for i in range(N):
    cities.append(list(map(int, sys.stdin.readline().split())))

for i in range(1, N+1):
    for j in range(100001):
        if j < cities[i][0]:
            dp[i][j] += dp[i-1][j]

        else:
            dp[i][j] += max(dp[i-1][j], cities[i][1] + dp[i-1][j - cities[i][0]], cities[i][1] + dp[i][j - cities[i][0]])

        if dp[i][j] >= C:
            ans = min(ans, j)
            break

        
print(ans)

3-3. C#

namespace boj_1106
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();

            int C = int.Parse(input[0]);
            int N = int.Parse(input[1]);

            int answer = 100001;

            int[,] dp = new int[N + 1, 100001];
            List<int[]> cities = new List<int[]>
            {
                new int[] { 0, 0 }
            };

            for (int i = 0; i < N; i++)
            {
                cities.Add(Array.ConvertAll(sr.ReadLine().Split(), int.Parse));
            }

            for (int i = 1; i < N + 1; i++)
            {
                for (int j = 0; j < 100001; j++)
                {
                    if (j < cities[i][0])
                        dp[i, j] += dp[i - 1, j];

                    else
                    {
                        dp[i, j] = (int)MathF.Max(dp[i - 1, j], MathF.Max(cities[i][1] + dp[i - 1, j - cities[i][0]], cities[i][1] + dp[i, j - cities[i][0]]));
                    }

                    if (dp[i, j] >= C)
                    {
                        answer = (int)MathF.Min(answer, j);
                        break;
                    }
                        
                }
            }

            sw.WriteLine(answer);
            sw.Close();
        }
    }
}