[17208] 카우버거 알바생

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

동적계획법으로 접근한 문제다.

---

풀이 방법

2차원 배열 dp를 생성. x열은 소유하고 있는 버거를, y행은 소유하고 있는 감자튀김이다.

따라서 dp[x][y]는 버거 x개와 감자튀김 y개를 가지고 있을 경우 받을 수 있는 최대 주문의 수를 의미한다.

 

M행 K열의 2차원배열을 생성해야 하는데, 인덱스로 접근하기 편하게 dp[M+1][K+1] 배열로 선언하였다.

 

입력된 주문이 버거 M개 혹은 감자튀김 K개를 초과한다면 해당 주문은 탐색할 필요가 없다.

 

dp[M][K]부터 dp[0][0]까지 역순으로 탐색하여 (동일 주문은 하나만 받을 수 있다.)

주문을 받지 않고 남아있는 음식을 아낄 것인지 (dp[x][y]) 혹은

해당 주문을 받을 것인지 (dp[x-현재 주문의 버거 개수][k-현재 주문의 감자튀김 개수]+1)

둘 중 더 큰 값을 선택하여 현재 탐색 중인 곳을 갱신하면 된다.

 

따라서 현재 보유 중인 버거가 x개, 감자튀김이 y개이며 현재 요청된 주문의 버거 개수가 dx, 감자튀김의 개수가 dy일 경우, 점화식은 다음과 같다.

dp[x][y] = max(dp[x-order.dx][y-order.dy]+1,dp[x][y])

---

정답 코드

	import Foundation
	let NMK = readLine()!.split(separator: " ").map{Int($0)!}
	let N = NMK[0]
	let M = NMK[1]
	let K = NMK[2]
	var arr = [(dx:Int, dy:Int)]()
	var dp = Array(repeating: Array(repeating: 0, count: K+1), count: M+1)
	var ans = 0
	for _ in 0..<N{
	let XY = readLine()!.split(separator: " ").map{Int($0)!}
	let X = XY[0]
	let Y = XY[1]
	arr.append((X,Y))
	}
	for i in 0..<N{
	let order = arr[i]
	for x in stride(from: M, through: 0, by: -1){
	for y in stride(from: K, through: 0, by: -1){
	if order.dx > x || order.dy > y { continue }
	dp[x][y] = max(dp[x-order.dx][y-order.dy]+1,dp[x][y])
	ans = max(ans, dp[x][y])
	}
	}
	}
	print(ans)

view raw 17208.swift hosted with ❤ by GitHub