[JAVA] 백준 7579 앱 - 골드3

 

 

주절거리는 서론

웬만하면 문제 하나를 티스토리 게시글로 올리지 않는데, 너무 재밌는 문제라서 올려본다.

dp를 어느정도 풀어봤다고 생각했는데, 이런 유형은 처음 접해서 너무 참신했다. dp를 조금 더 공부하고싶다는 생각이 들었다. 

 

 

 

문제 링크

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

2025-02-09 기준 푼 사람이 많다.

 

 

 

풀이 접근법

일반적인 dp 풀이로 들어가면 무조건 메모리가 터진다. 예를 들어, 필요한 바이트 수인 M을 구하기 위해 dp 배열을 만든다고 하면, 최대 100 * 10_000_000 = 10억 크기의 배열이 필요하다.

 

이 문제는 조금 변형해서 생각해야한다. 접근법은 다음과 같다.

 

특정 비용일 때 얻을 수 있는 최대 바이트 수를 dp배열에 저장

 

 

즉, 비용을 dp배열의 열로 만들고, dp배열의 값은 얻을 수 있는 최대 바이트 수를 저장한다.

문제에서 비용의 경우 최대 100 * 100 = 10000 개밖에 되지 않기 때문에 충분히 배열로 만들 수 있다. 

 

1. 특정 앱을 중지시킨다고 가정했을 때, 특정 비용일 때 얻을 수 있는 최대 바이트수를 저장
2. 비용을 구하다 원하는 비용을 찾는다면, 그 이후 비용은 고려하지 않아도 됨 -> minCostPlusOne 값에 저장하여 시간절약
3. 이후에는 비용 0 부터 minCostPlusOne 이전까지만 확인하여 최소 비용을 찾아냄
4. 정답은 minCostPlusOne-1

 

(minCostPlusOne 값을 +1해서 저장한 이유는 for문에 <=(등호)를 쓰기 싫어서이다. 큰 이유는 없다)

 

 

 

코드

class Main {
    static int[][] value;

    public static void main(String[] args) throws IOException {
    	//입력받기 -----------------
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int appCnt = Integer.parseInt(st.nextToken());
        int requiredByte = Integer.parseInt(st.nextToken());

        value = new int[appCnt][2];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < appCnt; i++) {
            value[i][0] = Integer.parseInt(st.nextToken()); //바이트 수
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < appCnt; i++) {
            value[i][1] = Integer.parseInt(st.nextToken()); //비용
        }
        //입력 끝 -----------------

		//선택할 앱을 행으로, 비용을 열로 잡음(나올 수 있는 최대 비용을 계산)
        int[][] dp = new int[appCnt + 1][appCnt * 100 + 1];
        
        //최소비용 + 1 값이 저장되는 변수
        int minCostPlusOne = dp[0].length;

        for (int i = 1; i < dp.length; i++) {
            int byteCnt = value[i - 1][0];
            int cost = value[i - 1][1];

            for (int j =0; j<minCostPlusOne; j++) {
                if (j - cost < 0) {
                    dp[i][j] = dp[i-1][j];
                    continue;
                }

                if (dp[i-1][j] < dp[i-1][j-cost] + byteCnt) {
                    dp[i][j] = dp[i-1][j-cost] + byteCnt;
					
                    //최적화를 위한 코드. 필요 바이트수를 넘어갔다면 이후 비용은 볼 필요가 없다
                    if (dp[i][j] >= requiredByte) {
                        minCostPlusOne = j+1;
                    }
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        System.out.println(minCostPlusOne-1);
    }
}

 

 

제출 결과

 

 

 

너무 재밌었따~!

 

 

 

 

참고한 블로그

혼자서는 못풀어서 다음 블로그를 참고했다

https://dragon-h.tistory.com/9