[DP] 백준 7579 앱 자바(java) 코드

BOJ 7579번 앱 문제 자바(java) 풀이

• 난이도: 골드3
• BOJ 7579번 앱
  
  
  

문제정리

1. 비활성화: 필요한 메모리가 부족해질때 스마트폰의 OS가 앱들 중 몇개를 삭제하는 과정
2. 비활성화된 앱들을 재실행할 경우 그만큼 시간이 더 필요하기 때문에 필요한 메모리만큼 비활성화 하는 것은 좋지 않다.
3. N개의 앱이 활성화 되어있다. 앱은 각각 m 바이트 만큼의 메모리를 사용하고 있다.
4. 앱을 비활성화한 후 다시 싫애하고자 할 경우 추가적으로 들어가는 비용은 c 이다.
5. 메모리 M이 추가로 필요하여 비활성화 하고자 할때 비용 c의 합이 최소가 되는 방법을 찾는다.
   
   
   

문제 풀이

다이나믹 프로그래밍 기법을 이용합니다.
모든 경우를 따져서 하기에는 시간이 부족하기 때문입니다.
이와 유사한 문제를 풀어봤던 것 같은데 잘 기억이 안나네요 ㅠㅠ
사실 처음에는 greedy 방식으로 풀었는데 이는 틀렸습니다가 나오는데 이유를 잘 모르겠습니다...
dp[i] : i cost를 이용해서 사용할 수 있는 최대 Memory를 저장합니다.

1. cost의 최대 값은 최대 10000이므로 배열의 크기를 10001로 잡습니다
2. 그리고 업데이트를 할때 값이 겹치지 않도록 하기 위해서 뒤에서 부터 확인해야 합니다.
3. dp 배열의 값이 -1이면 이전 cost에 더해질 필요가 없으므로 무시합니다.
4. 그렇지 않다면 cost만큼 뺀 이전 dp 값에서 현재 memory 값을 더한 것이 더 크다면 update 해줍니다.
5. 초기화를 위해서 메모리값이 -1인 경우 update 해줍니다. (base)
6. 그리고 가격이 제일 작은데 M 값을 넘는 경우를 찾는 것이므로 dp 배열 앞에서 부터 M이상인 값을 찾으면 cost i를 출력하고 프로그램을 끝냅니다.
   
   
   

프로그램 로직 따라가보기

예제의 경우 cost의 최대 값이 15이기 때문에 j를 15로 잡고 실행되는 것 처럼 따라해보겠습니다
꼭 저 처럼 직접 해보시길 바랍니다! 그래야 기억에 남을까 말까 하는것 같아요

5 60
30 10 20 35 40
3 0 3 5 4

1. 처음 cost 값은 3입니다. for문을 모두 돌지만 처음이기에 모두 -1이므로 update를 하지 않습니다.
2. 44번째줄 if문에서 dp[3] = 30으로 update 합니다.

   '-1' 값은 생략
   3: 30

3. 다음 cost 값은 0입니다. for문을 돌다가 j가 3인 부분에서 if문에 걸리지 않습니다. dp[j-cost]가 dp[3]이 됩니다.
   dp[3] + 10 > dp[3]이 되서 dp[3] 값이 40이 됩니다.
   그리고 dp[0] = 10이 됩니다.

   0: 10
   3: 40

4. 다음 cost 값은 3입니다.
   for문을 돌다가 j=6에서 if문에 걸리지 않습니다 dp[3]에 값이 있기 때문입니다.
   dp[3] + 20 > dp[6]을 검사하는데 dp[6]의 값이 -1이므로 dp[6] = 60이 됩니다.
   이 의미는 cost=3, mem=30인 앱과 cost=3, mem=20인 앱 두개를 비활성화 했을떄의 비용을 의미합니다.( 그 중에서도 MAX 값)

   0: 10
   3: 40
   6: 60

5. 다음 cost 값은 5입니다.
   for문을 돌다가 j=11에서 멈춥니다. j-cost=6으로 dp[6]의 값이 -1이 아닙니다.
   dp[11]의 값을 60 + 35로 update 합니다.
   j=8에서 dp[3] + mem[3]이 dp[8] 값 보다 크므로 update 합니다.
   j=5에서 dp[0] + mem[3]이 dp[5] 보다 크므로 update 합니다.

   0: 10
   3: 40
   5: 45
   6: 60
   8: 75
   11: 95

6. 마지막으로 cost가 4인 앱입니다.
   for문을 돌다가 j=15에서 dp[11] + m[4]가 dp[15] 보다 크기 때문에 update 합니다.
   j=12에서 dp[8] + m[4]가 dp[12]보다 크므로 update
   j=10에서 dp[6] + m[4]가 dp[10]보다 크므로 update
   j=9에서 dp[5] + m[4]가 dp[9]보다 크므로 update
   j=7에서 dp[3] + m[4]가 dp[7]보다 크므로 update
   j=4에서 d[0] + m[4]가 dp[4]보다 크므로 update

   0: 10
   3: 40
   4: 50
   5: 45
   6: 60
   7: 80
   8: 75
   9: 85
   10: 100
   11: 95
   12: 115
   15: 135

7. 앞에서 부터 M 이상인 값을 찾습니다. M은 60이므로 cost가 제일 작은 M은 6이됩니다. 따라서 답인 6을 출력하면 됩니다.

백준 7579번 앱 자바 코드

- 실행시간: 100 ms
- 메모리 13988 kb