[ALGOSPOT - SUSHI/JAVA] 회전초밥

https://algospot.com/judge/problem/read/SUSHI

algospot.com :: SUSHI

DP와 관련된 문제를 푼지 꽤 오래되어 어렵게 푼 문제이다.

 

처음에는 운영진의 예산만큼 배열을 만들어 DP로 풀려했지만 예산의 한도가 2,147,483,647인 것을 보고 DP가 아닌지 의심했다.

 

그러다 초밥의 가격이 항상 100의 배수인 것을 확인했다.

즉 초밥의 가격과 운영진의 예산을 100을 나눠버리면 된다는 뜻이다.

 

처음에는 Pair를 이용해 초밥의 가격과 선호도를 받고 이를 Vector에 저장했지만 시간초과가 발생했다.

그래서 Vector가 아닌 초밥의 가격과 선호도를 각각 배열을 선언해 따로 저장했다.

 

하지만 아무리 운영진의 예산에서 100을 나눠도 수가 너무 커 DP용 배열의 크기를 운영진의 예산으로 잡기에는 문제가 있었다.

 

생각해보니 초밥의 가격은 2만원 이하 심지어 100을 나누면 200원이라고 보면 된다.

어차피 초밥의 가격을 넘어서는 DP배열을 보지 않을 것이니 DP용 배열의 크기를 201로 잡았다.

 

    public static int DP() {
        dp[0] = 0;
        for (int i = 1; i <= m; i++) { //가격
            int sel = 0;
            for (int j = 0; j < n; j++) {
                if (i >= price[j])
                    sel = Math.max(dp[(i - price[j]) % 201] + prefer[j], sel);
            }
            dp[i % 201] = sel;
            result = Math.max(result, sel);
        }
        return result;
    }

처음에는 입력받은 초밥의 가격 중 최소값을 구해 i를 최소값 부터 시작할까 했지만 귀찮아서 아래 조건문으로 넣었다.

입력받은 초밥을 하나씩 보며 해당 초밥의 가격을 뺀 dp배열의 선호도에 해당 초밥의 선호도를 더한 값을 구하고 모든 초밥을 돌아보며 최대값을 넣어준다.

 

즉, sel은 모든 초밥을 한 번씩 보며 현재 가격에 해당하는 최대 선호도를 저장하는 변수이다.

result는 전체 최대 선호도를 저장하는 변수이다.

 

마지막 result를 출력하면 된다.

 

반응형

 

전체코드

import java.util.*;

public class Main {
    static int c, n, m;
    static int[] dp = new int[201];
    static int result = 0;
    public static int[] price = new int[20];
    public static int[] prefer = new int[20];

    public static int DP() {
        dp[0] = 0;
        for (int i = 1; i <= m; i++) { //가격
            int sel = 0;
            for (int j = 0; j < n; j++) {
                if (i >= price[j])
                    sel = Math.max(dp[(i - price[j]) % 201] + prefer[j], sel);
            }
            dp[i % 201] = sel;
            result = Math.max(result, sel);
        }
        return result;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        c = sc.nextInt(); //테스트 케이스 수
        for (int p = 0; p < c; p++) {
            result = 0;
            n = sc.nextInt(); //초밥 종류
            m = sc.nextInt() / 100; //예산
            for (int i = 0; i < n; i++) {
                price[i] = sc.nextInt() / 100;
                prefer[i] = sc.nextInt();
            }
            System.out.println(DP());
        }
    }
}