[백준 29704번 / java] 벼락치기

문제

29704번: 벼락치기 (acmicpc.net)

N개 T일 내에 제출 못 하면 벌금

벌금의 최소 금액을 출력하라

풀이

먼저 모든 조합을 찾는 방법을 생각했고, 다음으로 그리디를 떠올렸다.

 

그리디 기준 -> 벌금이 큰 날부터? 소요 일수가 작은 날부터?

객체를 만들어서 일수, 벌금을 저장한 후 리스트에 넣어 벌금 기준으로 정렬하고, 벌금이 같다면 소요 일수가 작은 순서로 정렬하기로 했다.

1. 벌금이 큰 순서로 정렬
2. 벌금이 같다면 소요 일수가 작은 순서로 정렬
3. 앞에서부터 (T >= 소요일수)이면 선택

 

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
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());

        List<Prob> probList = new ArrayList<>();
        int totalM = 0;

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            probList.add(new Prob(d, m));
            totalM += m;
        }

        Collections.sort(probList);

        for(int i=0; i<probList.size(); i++){
            Prob now = probList.get(i);
            if(T >= now.d){
                totalM -= now.m;
                T -= now.d;
            }else break;
        }

        bw.write(totalM + " ");
        bw.close();
    }
}
class Prob implements Comparable<Prob>{
    int d, m;
    Prob(int d, int m){
        this.d = d;
        this.m = m;
    }
    public int compareTo(Prob p){
        if(p.m == this.m){
            return this.d - p.d;
        }else{
            return p.m - this.m;
        }
    }
}

테케는 다 통과했는데 틀렸다. 그리고 알고리즘 분류를 확인했는데 dp 배낭문제였다.

내가 놓친 부분을 알기 위해 반례를 찾아보았다.

5 15
15 5000
7 4000
1 3000
5 2000
6 1000
위 코드로 이 반례를 실행하면 5,000원 안 내려고 15일을 다 쓰다가 10,000원을 내는 상황이 된다.

이 문제는 그리디로 풀면 안 된다. 

Knapsack Problem (배낭문제)는 dp문제로, 어떤 배낭이 있고 그 배낭 안에 넣을 수 있는 최대 무게가 K일 때

배낭에 넣을 수 있는 N개의 물건이 각기 다른 가치V, 다른 무게W를 지닌 경우 배낭에 최대한 가치가 높은 물건들을 담을 수 있는 조합을 찾는 문제이다. 

 

맨 처음 접근했던 것처럼 Brute Force로 가능한 모든 조합을 만들려면 2^N개의 경우의 수를 모두 시도해보아야 한다. 따라서 좋지 못한 방법이다. 그리디를 사용해도 마찬가지로 최적의 해를 찾을 수 없다.

 

따라서 dp를 사용해야 한다. dp에는 무게 w을 사용했을 때 얻을 수 있는 최대 가치가 저장된다. 

배낭에 물건을 넣을 때, 선택할 수 있는 경우는 두 가지 뿐이다. 

1. 물건을 넣는다

2. 물건을 넣지 않는다

따라서 dp에 들어갈 최대 가치를 정할 때 'i번째 물건을 넣지 않은 경우 얻을 수 있는 최대 이익'과 'i번째 물건을 넣기 위해 공간을 만든 후 얻을 수 있는 최대 이익 + i번째 물건을 넣어서 얻는 이익'를 비교하여 더 큰 값을 dp배열에 저장한다.

 

knapsack을 적용한 이 문제의 풀이법은 다음과 같다. 

 

2차원 dp배열을 생성해서 열에는 모든 문제들을, 행에는 일수를 둔다.
dp[t] = t일을 소요했을 때 얻을 수 있는 이익의 최대값

dp[t] = max(t일을 확보했을 때 최대 이익+t일을 써서 지금 문제 해결했을 때 이익, 지금 문제를 제외하고 구한 전 단계의 최대 이익)
점화식 : dp[i][t] = max(dp[i-1][t-ti]+vi, dp[i-1][t])

 

그리고 이 점화식을 사용한 코드는 다음과 같다.

코드 1 - 이차원배열 dp

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

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 totalCost = 0;
        int[][] dp = new int[N+1][T+1];

        //0행 0열 초기화
        Arrays.fill(dp[0], 0);
        for(int i=0; i<N; i++){
            dp[i][0] = 0;
        }

        for(int i=1; i<=N; i++){
            st = new StringTokenizer(br.readLine());
            int day = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            totalCost += cost;

            for(int j=1; j<=T; j++){
                if(j<day){
                    dp[i][j] = dp[i-1][j];
                }else dp[i][j] = Math.max(dp[i-1][j-day]+cost, dp[i-1][j]);
            }
        }

        bw.write(totalCost - dp[N][T]+" ");
        bw.close();

    }
}

 

메모리를 아끼기 위해 dp를 1차원 배열로 쓰는 방법도 있다.

그러나 1차원 배열을 사용할 때는 dp를 역순으로 업데이트해야한다.

그래야 현재 고려 중인 물건을 중복으로 고려하지 않게 된다.

(간단한 예제로 직접 구해보면 원리를 알 것이다.)

코드 - 일차원배열 dp

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

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 totalCost = 0;
        int[] dp = new int[T+1];

        for(int i=1; i<=N; i++){
            st = new StringTokenizer(br.readLine());
            int day = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            totalCost += cost;

            for(int j=T; j>=day; j--){
                dp[j] = Math.max(dp[j], dp[j-day]+cost);
            }
        }

        bw.write(totalCost - dp[T]+" ");
        bw.close();

    }
}

Note

• knapsack문제를 미루고 있었는데 드디어 제대로 공부해보았다.
• 스터디를 통해 일차원 배열 사용하는 방법도 얻어가서 기본적이지만 꽤 유익했던 문제였다.