알고리즘/백준
[JAVA] 백준 7579 앱 - 골드3
fladi
2025. 2. 9. 20:24
728x90
주절거리는 서론
웬만하면 문제 하나를 티스토리 게시글로 올리지 않는데, 너무 재밌는 문제라서 올려본다.
dp를 어느정도 풀어봤다고 생각했는데, 이런 유형은 처음 접해서 너무 참신했다. dp를 조금 더 공부하고싶다는 생각이 들었다.
문제 링크
https://www.acmicpc.net/problem/7579
풀이 접근법
일반적인 dp 풀이로 들어가면 무조건 메모리가 터진다. 예를 들어, 필요한 바이트 수인 M을 구하기 위해 dp 배열을 만든다고 하면, 최대 100 * 10_000_000 = 10억 크기의 배열이 필요하다.
이 문제는 조금 변형해서 생각해야한다. 접근법은 다음과 같다.
특정 비용일 때 얻을 수 있는 최대 바이트 수를 dp배열에 저장
즉, 비용을 dp배열의 열로 만들고, dp배열의 값은 얻을 수 있는 최대 바이트 수를 저장한다.
문제에서 비용의 경우 최대 100 * 100 = 10000 개밖에 되지 않기 때문에 충분히 배열로 만들 수 있다.
- 특정 앱을 중지시킨다고 가정했을 때, 특정 비용일 때 얻을 수 있는 최대 바이트수를 저장
- 비용을 구하다 원하는 비용을 찾는다면, 그 이후 비용은 고려하지 않아도 됨 -> minCostPlusOne 값에 저장하여 시간절약
- 이후에는 비용 0 부터 minCostPlusOne 이전까지만 확인하여 최소 비용을 찾아냄
- 정답은 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);
}
}
제출 결과
너무 재밌었따~!
참고한 블로그
혼자서는 못풀어서 다음 블로그를 참고했다
728x90