[백준/Swift] 7579: 앱. 문제 뿌수기!! | PS일지

문제

7579번: 앱

간단한 문제 요약

스마트폰에서 화면은 작다. 보이는 화면에서 '실행중'인 앱은 한 개 이지만, 더 많은 앱이 '활성화' 되어있다. 활성화 된 앱은 system resource memory를 사용한다. 

 

한 번이라도 실행됬던 앱들을 종료하지 않는 이상, 이미 활성화 된 앱으로 분류된다. 새로운 앱을 실행시켜야 하는데 이미 활성화 된 앱은 각각의 메모리를 점유하고 있다. 활성화 상태의 앱을 비활성화 시키면 특정 앱이 소유하고 있던 메모리가 반환되어 사용할 수 있다. 하지만 비활성화 된 앱들을 재 실행할 경우 그만큼 시간이 더 든다. 이를 추가비용 c 라고 한다. 현재 활성화 된 앱은 A (1...n) n가지 있고 각각의 앱은 m (1...n)의 메모리를 사용한다.

 

활성화 되어있는 앱 중 몇개를 비활성화 했을 때 발생되는 추가비용 c 합을 최소화 하여 필요한 메모리 M 바이트를 확보해야 한다.

 

고려해야 할 사항

• 각각의 활성화 된 앱이 점유하고 있는 메모리 m == 1 ~ 10,000,000
• 각각의 활성회 된 앱 -> 비활성화 -> 활성화 추가비용 c = 0 ~ 100

문제 풀이

"이 문제를 어떻게 dp로 연결지을 수 있을까..." dp는 참 어려운 것 같습니다 ㅠ.

 

문제 input은 활성화 된 앱이 각각 점유하고 있는 메모리와 추가비용 c의 값을 줍니다. 그리고 새로 실행해야 할 앱이 필요한 메모리 값M을 줍니다.

 

처음의 접근은 새로 실행해야 할 앱이 필요한 메모리 값(줄여서 M이라 하겠습니다.) M을 구하는 방법에 대한 고민이었습니다. 여러 개의 앱을 선택해서 비활성화 했을 때 반환된 메모리의 누적 값이 M이 되면 됩니다.

 

sub problem으로 나누기 위해 메모리 값이 가장 작은 1일 때부터... M까지 특정 앱들을 선택해서 비활성화 하는 방법을 생각했습니다. 근데 문제에서 특정 앱의 메모리 바이트 M = 10,000,000이 될 수 있다고 합니다. 그리고 앱의 개수 최대 N = 100

0~100개의 앱을 비활성화 하면서 1...10,000,000 메모리에서 특정 추가비용c를 구해간다면 100*10,000,000 많은 연산이 발생합니다. 그래서 다른 방법을 생각해야 합니다. 

 

각각의 앱은 메모리m를 점유하고 동시에 추가비용c을 갖고 있습니다. 추가비용은 100입니다. 최악의 경우 각각의 앱의 추가비용이 100일 때 100 100 100... 100 (n개의 앱 == 최대 100개의 앱) = 100*100 == 10,000. 즉 최악의 경우 100개의 앱을 비활성화 했을 때 추가비용이 최대 10,000입니다. 10,000 비용에 포함되는 값을 구하기 위해 작은 문제로 나눈 1부터 10,000까지 각각의 앱 최대 100개.. == 10,000* 100 작습니다!

 

그렇다면 기준은 최악의 경우인 10,000 추가비용에 대해 문제를 작게 나누어 "추가비용 1일 때 몇 개의 앱을 선택해야 하는가?" 로 정할 수 있습니다. 그리고 해당 선택된 앱이 반환할 메모리 또한 누적으로 저장해야 합니다. n의 추가비용일 때 선택된 메모리 누적 값은 재사용 될 수 있습니다. 그래서 dp table에는 메모리 누적 값이 들어갑니다.

 

 

 

이제 문제는 "앱을 어떻게, 몇 개 선택해야 하는가?" 입니다.

한 가지 떠오르는 방법은 앱 list의 앱 하나 하나에 대한 추가비용 1...10,000까지 각각의 특정 추가 비용에 대해 누적할 수 있는 메모리 최대치를 기록해 나가는 것입니다.

 

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

예제 입력값입니다.

 

app 1 을 선택할 경우(== 비활성화한다는 뜻) 30 메모리 반환, 추가비용 3 발생.

app 2 선택할 경우 10 메모리 반환, 추가비용 0 발생.

app 3 비활성화 할  경우(선택한다는 뜻) 20 메모리 반환, 추가비용 3 발생.

...

 

 

5개의 앱이 활성화 된 상태이고 각각의 앱은 memory, cost를 갖고 있습니다.

주어진 입력값에 대해 최악의 경우는 모든 앱을 다 비활성화 한 메모리를 반환해야 새로운 앱 을 실행할 수 있는 경우입니다. 위에서 언급했지만 이런식으로 다가 10억의 계산과정이 필요해서 추가비용을 기준으로 잡았습니다. 최악의 경우 3+0+3+5+4 = 15의 추가비용이 드는 경우입니다.

 

추가비용 0...15까지 각각의 특정 추가비용을 cost라고 부르겠습니다. 각각의 cost에 대해 앱을 한 개씩 비활성화 하는 경우에 대한 비용 측정을 해야합니다.

 

가장 먼저 생각해야 할 것은 새로운 앱을 실행하지 않는 경우입니다. 이 경우 app = 0 으로 정하겠습니다. table은 dp.

0 ... 15는 0부터 15까지 순차적으로 탐색하면서 특정 추가비용(cost)일 때 지정된 cost 이내에, 몇 개의 앱을 선택한 값의 추가 비용 누적 값이 cost를 넘지 않는 경우 이에 대한 앱들의 메모리가 저장됩니다.

 

맨 처음에는 활성화 된 앱을 전부 선택하지 않는 경우입니다. 이 경우 메모리를 반환하지 않습니다. (아무것도 비활성화 된 앱을 선택하지 않았으니까요)

 

 

이젠 첫 번째 활성화 된 앱 app1의 경우에 대해 추가비용 0...15 의 특정 cost에 대해서 비활성화 했을 때 발생한 추가비용 c1의 값3이 특정 cost보다 작으면 table의 값을 갱신해나갈 것입니다.

app1의 memory = 30, 추가비용 = 3입니다.

 

1. "특정 cost 0한도 내 app1을 선택할 수 있는가?"

no. app1은 3 cost이므로 특정 cost 0 보다 큽니다. 

dp[app1][0] = 0 (메모리 반환 x)

 

2. 특정 cost1, 2 또한 마찬가지입니다.

3. "특정 cost 3 한도 내 app1을 선택(==비활성화)할 수 있는가?"

yes. app1은 cost 3의 추가 비용을 발생하지만 비활성화 될 때 30 메모리를 반환합니다.

dp[app1][3] = 30

 

4. "특정 cost 4 한도 내 app1을 선택할 수 있는가?"

yes. 위의 경우와 마찬가지입니다. 이때 app1은 특정 cost 3이 발생합니다. 4 - 3 = 1. 하지만 아직 1 한도가 남았습니다. 그렇다면

dp[app1][4] = 30(app1의 반환 메모리) + _____ // 1이 남는데...

이 언더바에 들어가야 할 내용입니다. 1이 남으므로

언더바에는 dp[app1][4-1] 인 dp[app1][1] 이 들어가야 할까요? 0인데,, 이 개념은 "특정 cost 6 한도 내 app1을 선택할 수 있는가?"를 고려해봐야 합니다.

6 - 3 = 3. 즉 app1을 사용할 때 발생한 추가비용 3을 썼음에도 6 - 3 = 3이나 그 이하의 비용이 발생하는 앱을 선택할 수 있습니다.

여기서 dp[app1][6-3] == dp[app1][3] 이렇게 하는 경우가 맞을까요? 이 경우는 app1이 3일 때, app1을 선택한 경우입니다. 즉 dp[app1][6-3]이란 표현은 app1 두 번 선택한 느낌이 됩니다. 앱은 한개만 있는데. [6-3]은 이미 app1을 선택한 경우라고 볼 수 있습니다. 그리고 app1이 사용중인 메모리 30도 더했습니다. 그래서 남은 3은 app1이 아닌. app2,3,4,5 중 하나를 택하면 됩니다. 근데 저는 포문을 사용했기에 app1 이전의 경우 app(x)의 경우를 사용할 것입니다. 

 

다시 특정 cost 4로 돌아가서

 

dp[app1][4] = 30 + dp[app1][4-3] 이 아니라. 이전의 경우.

dp[app1][4] = 30 + dp[app1-1][4-3]을 사용할 것입니다. 즉 30의 메모리 반환은 노란색 밑줄 3의 비용을 발생하는 app1을 선택한 경우라고 볼 수 있습니다.(선택 ==비활성화..) 그리고 dp[app1 - 1][1(4-3)] 은 app1의 위에 있는 앱(appx)의 경우를 선택했을 때, 특정 추가비용 1일 때 반환된 최대 메모리 누적 값을 사용합니다. 근데 0입니다.

따라서 dp[app1][4] = 30 + dp[app1 - 1][1] = 30

dp[app1][5] = 30 + dp[app1-1][2] = 30

...

즉 여기까지 요약하자면, 이 테이블에는 특정 비용 0...15일때 앱 appx or app1을 선택했을 때 누적된 메모리 최대치를 담고 있습니다. 그리고 app1은 0...15에서 특정 cost일 때(ex 7) 자신을 선택했을 때(비활성화) 발생된 추가비용 3 이외에 남은 비용 (7-3) = 4 만큼의 추가비용을 추가비용 4일 때 appx에서 메모리 최대 누적 값을 사용합니다.

 

 

 

이제 선택할 것은 두 번째 앱입니다.

app 2 의 메모리 반환은 10입니다. 그리고 추가비용은 0 입니다.

특정 추가비용 이 0일 때 app2는 선택할 수 있습니다. app2의 cost = 0이기 때문입니다.

1,2,3,4,5,6... 각각의 특정 추가비용일 때 마찬가지입니다.

하지만 대표적으로 3의 경우를 생각해보겠습니다.

 

특정 추가비용 한도가 3일 때,

app2를 선택하는 경우에 발생하는 추가비용은 0입니다. 

dp[ app 2 ][3] = dp[app2][3 - 0] + 10.

하지만 위에서 설명했듯 dp[app2][3 - 0]에서 dp[app2]라는 개념은 자기자신을 또 선택하는 느낌입니다. 앱을 선택함으로 (추가비용 0을 제거해줌) 동시에 앱은 비활성화 상태가 되며 자신이 보유한 메모리 10을 반한하는데 또 dp[app2]를 쓰면 자신의 경우를 활용하는 것과 같기에  자신 위에있는 경우를 사용해야 한다고 설명했습니다.

dp[ app 2 ][3] = 10 + dp[app2 - 1][3 - 0 ] == dp[app 1 ][3] + 10 == 30 + 10.

 

이번엔 특정 추가비용 한도가 6일 때,

app 2 를 선택하는 경우.

dp[app 2][6] = 10 + dp[app2 -1][6-0] == dp[app 1][6] + 10 . 근데 위에서 여기서 dp[app1][6]은 위에서 설명했지만.

app 1을 선택했을 때 발생되는 추가비용 3. dp [app1][6 - 3] == dp[app1][3] 자기자신을 사용하는 경우이기에 dp[app1 - 1][6 -3] + 30. 자기 자신 app1 선택하면서 발생된 추가비용3과 이때 반환된 메모리 30 그리고 자신의 위에있는 앱을 선택한경우.. appx.의 최대 누적 메모리 값이라는 것을..

즉 dp[app2][6] 은 app2, app1, app0을 선택하는 경우입니다. 그래도 특정 한도 cost 6 이내에 3개를 선택하고도 남는 특정 비용값이라는 것입니다. 

사실 여기서 특징은 app 3을 선택했을 때도 특정 추가비용이 app 3의 추가비용보다 크거나 같을 때, 남은 추가비용에 대해 위에 앱에서 구한 최대 누적 메모리를 활용한다는 것입니다... 대박신기.. 이게 dp인 것 같습니다.

 

 

 

두 가지 경우만 살펴보겠습니다.

app 3은 추가비용 3 발생과 동시에 20 메모리를 반환합니다.

 

특정 한도 비용이 0인 경우. 

dp[app 3][0] = dp[app 3 - 1][0 - 3] 삐빅. 오류입니다. index 가 -3을 가리킵니다.

 

사실 여기서 조건이 붙습니다

 

if i(특정 비용) - 3(app3의 비용) >= 0 {
	dp[app 3][i] = dp[app 3 - 1][i - 3]
}

or

for app in appLists{
	for cost in costs where cost -  app비용저장List[app-1] >= 0 {
    	...
    }
}

 

where 키워드 관련 글..

 

if 문에서 걸러야 합니다. 근데 또 한가지 고려해야 할 점이 있습니다.

cost 0일 때 app 3을 사용할 수 없다. 그렇지만 app 2일 때 cost 0 이므로 app 2를 선택해도 cost == 0이므로 dp table의 목표인 최대 누적 메모리 에도 도달할 수있습니다.

 

포문 {
	if i(특정 비용) - 3(app3의 비용) >= 0 {
        dp[app 3][i] = dp[app 3 - 1][i - 3]
    }
    dp[app 3][i] = max( dp[app 3][i], dp[app 3 - 1][i])
}

max() 함수 안에 있는 두 경우는 app 3을 선택했을 때 최선의 메모리 누적 값이 되는 것인가? (현재로써는 app 3은 추가비용 3 덕분에 메모리 반환 0. cuz if문 실행 x) or dp[app 3 -1] 3 이전의 앱 app2, app1, appx의 cost 0일 때 최대 메모리 누적 경우가 더 큰가? 를 고려해서 갱신해야 합니다.

 

그리고 또 특정 비용 6한도 이하일 때.

 

app 3 을 선택하면 3의 비용이 남습니다.

이는 dp[app 3][6] = dp[app3 - 1][6-3] + 20.

dp[app 2][3]. 즉 특정 비용 3 한도내 메모리 최대 경우 app1과 app2 선택하는경우 40을 추가합니다. == 60 굿.

사실 여기까지 계산하고 이에 맞는 특정 비용한도 6을 답으로 체크해도 됩니다.

이런 느낌입니다.

 

코드

import Foundation

// MARK: - Properties
let nm = readLine()!.split{$0==" "}.map{Int(String($0))!}

let needMemory = nm[1]
let appMemoryLists = readLine()!.split{$0==" "}.map{Int(String($0))!}
let costs = readLine()!.split{$0==" "}.map{Int(String($0))!}
let maximumCost = costs.reduce(0, +)

// MARK: - Helpers
// 여기서 app -1을 한 이유는 app x일 때를 고려했기에,, dp의 값 dp[0] = 전부 0으로 초기화 한 점.
// 실질적인 앱 선택은 dp[1] 부터 dp[n] 까지입니다.
func solution() {
    let n = appMemoryLists.count
    var dp = Array(repeating: Array(repeating: 0, count: maximumCost+1), count: n+1)
    defer {print("\(dp[n].firstIndex(where: {$0>=needMemory})!)")}
    for app in 1...n {
        for cost in 0...maximumCost {
            if cost - costs[app-1] >= 0 {
                dp[app][cost] = dp[app-1][cost - costs[app-1]] + appMemoryLists[app-1]
            }
            dp[app][cost] = max(dp[app][cost], dp[app-1][cost])
        }
    }
}

solution()