5540 : 夜店 (Night Market) - JAVA, c#, C++

 

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

 

문제를 대충 해석해보면, 불꽃놀이와 야시장을 즐기고, 한정된 시간에 따른 야시장과 불꽃놀이의 최대 즐거움을 출력해내는 배낭 문제이다.

다만 t라는 제한 내에 놀이를 즐길수 있고, s시간에 불꽃놀이가 개최되는데 이를 무시할수가 없다.

그것을 고려하고 베낭 dp 반복문에 제한 사항을 둬야 하는데 이게 생각해내기 쉽지 않았다.

처음에는 불꽃놀이를 보는 시간에는 계승을 하고, 보지 않는 시간에는 최댓값 비교를 통해 값을 갱신했는데, 틀렸다. 왜냐하면 현재 진행되는 상점 들르면서 발생한 즐거움이 이전 상점 들르면서 발생한 즐거움보다 클수도 있다는 사실을 간과했기 때문이다.

 

그것을 일단 해결한 소스코드는 다음과 같다.

for(int i = 1; i <= n; i++){
            for(int j = 1; j <= t; j++){
                dp[i][j] = dp[i-1][j];
                dp[i][j] = Math.max(dp[i][j], dp[i][j-1]);
                if(j>=jikan[i] && !(j-jikan[i] < s && j>s)){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-jikan[i]]+tanoshi[i]);
                }
            }
        }

일단 특정 지점을 들렀다는 사실은 변하지 않기에 해당 부분을 계승한다.

이전 지점의 계승값과, 현재 들른 야시장의 즐거움을 비교하여 큰 값을 dp배열에 넣는다.

값이 크다면, 해당 부분이 변경되고 변경된 루트로 가야 최댓값을 얻을수 있기 때문이다.

배낭 문제의 성질인 무게(시간)가 크거나 같을때, 그리고 불꽃놀이를 고려하여 해당 조건을 설정했다.

불꽃놀이가 시작되고나서부터 끝날때까지는 야시장을 들를수 없기에 야시장 들르는것을 차단해놨다. 

야시장 들르는 기준을 헷갈려서 헤맨 문제이다.

 

소스코드는 다음과 같다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());
        int[] tanoshi = new int[n+1];
        int[] jikan = new int[n+1];
        int[][] dp = new int[n+1][t+1];
        for(int i = 1; i <= n; i++){
            st = new StringTokenizer(br.readLine());
            tanoshi[i] = Integer.parseInt(st.nextToken());
            jikan[i] = Integer.parseInt(st.nextToken());
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= t; j++){
                dp[i][j] = dp[i-1][j];
                dp[i][j] = Math.max(dp[i][j], dp[i][j-1]);
                if(j>=jikan[i] && !(j-jikan[i] < s && j>s)){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-jikan[i]]+tanoshi[i]);
                }
            }
        }

        bw.write(String.valueOf(dp[n][t]));
        bw.flush();
        bw.close();
        br.close();

    }
}

 

소스코드(C++)

#include <bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3007;
int n, t, s;
int dp[maxn][maxn];
int A[maxn], B[maxn];

int main(){
	cin >> n >> t >> s;

	for(int i = 1; i <= n; i++)
        cin >> A[i] >> B[i];

	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= t; j++){
			dp[i][j] = dp[i - 1][j];
			dp[i][j] = max(dp[i][j], dp[i][j - 1]);

			if (j >= B[i] && !(j - B[i]<s && j>s))
				dp[i][j] = max(dp[i][j], dp[i - 1][j - B[i]] + A[i]);
		}

	cout << dp[n][t] << endl;

	return 0;
}

 

소스코드(C#)

using System;

public class Program
{
    const int maxn = 3007;
    static int n, t, s;
    static int[,] dp = new int[maxn, maxn];
    static int[] A = new int[maxn];
    static int[] B = new int[maxn];

    public static void Main()
    {
        string[] input = Console.ReadLine().Split();
        n = int.Parse(input[0]);
        t = int.Parse(input[1]);
        s = int.Parse(input[2]);

        for(int i = 1; i <= n; i++)
        {
            input = Console.ReadLine().Split();
            A[i] = int.Parse(input[0]);
            B[i] = int.Parse(input[1]);
        }

        Array.Clear(dp, 0, dp.Length);

        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= t; j++)
            {
                dp[i, j] = dp[i - 1, j];
                dp[i, j] = Math.Max(dp[i, j], dp[i, j - 1]);

                if(j >= B[i] && !(j - B[i] < s && j > s))
                {
                    dp[i, j] = Math.Max(dp[i, j], dp[i - 1, j - B[i]] + A[i]);
                }
            }
        }

        Console.WriteLine(dp[n, t]);
    }
}