[AlgoSpot] 회전초밥

문제 설명

알고리즘 문제 해결 전략 - 동적 계획법
https://algospot.com/judge/problem/read/SUSHI

문제 풀이

• 동적 계획법 문제이다.
• 우선 recursive한 구현으로 접근하면 메모이제이션을 위한 배열의 크기가 20억이 넘기 때문에 recursive하게 구현할 수 없다. (다른 방법이 있을수도..?)
• Iterative한 구현을 이용했을 때 장점인 슬라이딩 윈도우 방식을 사용하면 풀이가 가능하다.

  슬라이딩 윈도우

  • 특정 구간에서 메모이제이션에 필요한 부분이 전체에 일부일때 해당 부분을 옮겨 가며 저장하는 것

• 이 문제에서 사용할 수 있는 점화식은 아래와 같다.

  • dp[가격의합] = 해당 가격의합에서 최대 만족도
  • dp[가격의합] = max(dp[가격의합 - 특정 물건의가격] + 특정물건의 만족도)

• 위와 같이 점화식을 구성할때, 최대 수행해야하는 loop 횟수는 가격에 비례(21억)하기 때문에 시간초과가 발생할 가능성이 크다.
• 이를 위해 문제의 조건인 100의 배수라는 점을 이용해 모든 가격을 100으로 나누면 충분히 수행 가능하다.

소스 코드 (JAVA)

import java.util.Arrays;
import java.util.Scanner;

import javax.sound.sampled.SourceDataLine;

public class Main {

    public static int C, N, M;
    public static int[] price = new int[20];
    public static int[] value = new int[20];
    public static int[] dp = new int[201];

    //iterative 형식 dp 
    public static int solve() {
        int res = 0;
        dp[0] = 0;
        for (int i = 1; i <= M; i++) {
            int cand = 0;
            for (int j = 0; j < N; j++) {
                if (i >= price[j])
                    cand = Math.max(cand, dp[(i-price[j]) % 201] + value[j]);
            }
            dp[i % 201] = cand;
            res = Math.max(res, cand);
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        C = sc. nextInt();
        for (int c = 0; c < C; c++) {
            N = sc.nextInt();
            M = sc.nextInt() / 100;
            for (int i = 0; i < N; i++) {
                price[i] = sc.nextInt() / 100;
                value[i] = sc.nextInt();            
            }
            System.out.println(solve());
        }
    }
}