[Swift] 백준 DP 문제 풀이 (2839, 1463, 1003, 11726, 9465, 1890, 12865, 15486)

🥺 DP가 너무 약한자의 DP 조지기

https://github.com/tony9402/baekjoon/tree/main/dynamic_programming_1

https://github.com/tony9402/baekjoon/tree/main/dynamic_programming_2

 

해당 링크의 문제들을 도장깨기 하듯? 풀었고 풀이는 주석으로 달아두었습니다. 

2839

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

 

내 풀이

import Foundation

let n = Int(readLine()!)!
var dp = Array(repeating: 0, count:5001)

for i in 3...n {
  if i%3 == 0 {
    dp[i] = dp[i-3] + 1 // 3으로 나누어떨어질때, 설탕봉지를 들고가는 경우의 수는 3을 더하기 이전의 설탕 봉지수 + 1
  }

  if i%5 == 0 {
    if dp[i] != 0  {
      dp[i] = min(dp[i], dp[i-5]+1) // 같은 방식으로, 3으로 나누어떨어질때와 5로 나누어떨어질때의 최소값 비교  
    } else {
      dp[i] = dp[i-5] + 1
    }
  }

  if dp[i-3] != 0 && dp[i-5] != 0 { // 3과 5의 조합으로 설탕을 가져갈 수 있을 때
    if dp[i] != 0 {
      dp[i] = min(dp[i], min(dp[i-3], dp[i-5])+1)
    } else {
      dp[i] = min(dp[i-3], dp[i-5])+1
    }
  }
}

if dp[n] == 0 {
  print(-1)
} else {
  print(dp[n])
}

 

1463

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

 

내 풀이

import Foundation

let n = Int(readLine()!)!
var dp = Array(repeating:0, count: n+1)

if n == 1 {
  print(dp[n])
  exit(0)
}

for i in 2...n {
  dp[i] = dp[i-1] + 1 // 1을 뺐을 때의 경우의 수
  
  if i%2 == 0 {
    dp[i] = min(dp[i], dp[i/2]+1) //1을 뺀것과 2로 나눈 연산 중 최솟값 구한 다음
  }

  if i%3 == 0 {
    dp[i] = min(dp[i], dp[i/3]+1) //위 최소값과 3으로 나눈 연산 중 최솟값 구하기
  }
}

print(dp[n])

 

reference

https://jae04099.tistory.com/199

[파이썬] 백준 - 1463: 1로 만들기 (매우 자세한 해설 포함)

 

1003

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

 

내 풀이

import Foundation

var dp = Array(repeating:(0, 0), count:41) //각각 0, 1 차례대로 튜플
dp[0] = (1, 0)
dp[1] = (0, 1)

for i in 2...40 {
  dp[i].0 = dp[i-1].0 + dp[i-2].0
  dp[i].1 = dp[i-1].1 + dp[i-2].1
}

let t = Int(readLine()!)!
for _ in 0..<t {
  let n = Int(readLine()!)!
  print("\(dp[n].0) \(dp[n].1)")
}

 

11726

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

 

내 풀이

import Foundation

let n = Int(readLine()!)!
var dp = Array(repeating: 0, count:1001)
// DP 테이블 : 2xi 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수
dp[1] = 1
dp[2] = 2

for i in 3...1000 {
  dp[i] = (dp[i-1] + dp[i-2]) % 10007
}

print(dp[n])

 

dp[3]와 dp[4] 즉 2x3 2x4 타일을 만드는 방법은 아래 그림과 같다. 이로부터 점화식을 dp[i] = dp[i-1] + dp[i-2] 가 성립함을 알 수 있음 (dp[3] = dp[2] + dp[1], dp[4] = dp[3] + dp[2])

9465

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

 

내 풀이

import Foundation

let t = Int(readLine()!)!
var dp:[[Int]] = []
var n = 0

for _ in 0..<t {
  n = Int(readLine()!)!
  dp = []
  
  for _ in 0..<2 {
    dp.append(readLine()!.split(separator:" ").map { Int($0)! })
  }

  simulation()
}

func simulation() {
  if n == 1 {
    print(max(dp[0][0], dp[1][0]))
    return
  }
  dp[0][1] += dp[1][0]
  dp[1][1] += dp[0][0]

  for i in 2..<n {
    dp[0][i] += max(dp[1][i-1], dp[1][i-2]) 
    dp[1][i] += max(dp[0][i-1], dp[0][i-2])
    // 여기서 dp[0][i]가 dp[0][i-2]에 대한 고려가 없는 이유는, dp[1][i-1]에 dp[0][i-2]를 고려하여 최대값을 가지고있기 때문에 고려할 필요 X
  }
  print(dp.flatMap { $0 }.max()!)
}

 

1890

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

1890번: 점프

import Foundation

let n = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count:n), count:n) 
var board:[[Int]] = []
for _ in 0..<n {
  board.append(readLine()!.split(separator:" ").map { Int($0)! })
}
dp[0][0] = 1

func validBound(_ i:Int, _ num: Int) -> Bool {
  if i + num < n {
    return true
  } else {
    return false
  }
}

// DP 테이블: i와 j까지 갈 수 있는 경로의 수
for i in 0..<n {
  for j in 0..<n {
    if i == n-1 && j == n-1 {
      print(dp[i][j])
      break
    }
    
    if validBound(i, board[i][j]) {
      dp[i+board[i][j]][j] += dp[i][j]
    }
    // dp[i][j]에 이미 i와 j까지 가기까지의 경로가 있으므로, 해당 경로의 수를 더해주면 곧 경우의 수가 됨

    if validBound(j, board[i][j]) {
      dp[i][j + board[i][j]] += dp[i][j]
    }
  }
}

 

12865 (냅색 알고리즘)

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

12865번: 평범한 배낭

- 냅색 알고리즘: 여러 가지 사항이나 물체가 있을 때, 특정한 조건을 만족하는 조합을 구하는 문제

 

- DP[i][j] 테이블 정의

i를 물건의 순서, j를 현재 배낭에 넣을 수 있는 kg의 한계?라고 정해두고 표를 채우면 다음과 같다.

		1	2	3	4	5	6	7
0	(6, 13)	0	0	0	0	0	13	13
1	(4, 8)	0	0	0	8	8	13	13
2	(3, 6)	0	0	6	8	8	13	14
3	(5, 12)	0	0	6	8	12	13	14

1) j보다 물건의 무게가 더 큰 경우 (즉 배낭에 담을 수 없는 경우) -> j < w

- 물건을 담을 수 없으므로, 똑같은 무게에서 그 이전까지의 물건을 따졌을 때의 최대값을 그대로 가져온다.

 

2) j가 물건의 무게보다 크거나 같은 경우 (즉 배낭에 담을 수 있는 경우) -> j>=w

- 물건을 담을 수 있으므로, 해당 물건을 넣지 않았을 때 (dp[i-1][j]) 와 해당 물건을 넣었을 때의 가치를 비교해야한다.

- 이 때 어떤 물건을 넣으려면 이전의 물건을 같이 넣었을 때의 가치로 판단해야하므로 (가치는 모두 양수)

현재 배낭의 무게에서 물건의 무게를 뺀, 즉 다른 물건과 같이 넣는 경우의 최대값에 가치를 더해서 두개를 비교한다.

import Foundation

let nk = readLine()!.split(separator:" ").map { Int($0)! }
let n = nk[0], k = nk[1]

var dp = Array(repeating: Array(repeating:0, count: k+1), count:n+1)
var arr:[(Int, Int)] = [(0, 0)]
for _ in 0..<n {
  let input = readLine()!.split(separator:" ").map { Int($0)! }
  arr.append((input[0], input[1]))
}

for i in 1...n {
  for j in 1...k {
    let (w, v) = arr[i]

    if j >= w { // j가 현재 담으려는 물건의 무게보다 크거나 같으면
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v) // 바로 이전의 dp값과 다르물건과 자기 자신을 더했을 때의 가치를 비교함

    } else {
      dp[i][j] = dp[i-1][j] // 이전 값 그대로 가져옴
    }
  }
}

print(dp[n][k])

 

15846

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

 

내 풀이

import Foundation

let n = Int(readLine()!)!
var arr:[(Int, Int)] = [(0, 0)] // 껍데기

var dp = Array(repeating: 0, count:n+1) // 최대 수익 DP 테이블, i: 기간

for _ in 1...n {
  let input = readLine()!.split(separator:" ").map { Int($0)! }
  arr.append((input[0], input[1])) // 상담을 하는데 필요한 기간, 이익
}

for i in 1...n {
  dp[i] = max(dp[i-1], dp[i]) // 자기 날짜의 기존 수익 값과 이전까지 일했을 때의 값이 곧 그날까지 얻을 수 있는 수익의 최대값
  let dur = i + arr[i].0 - 1
  if dur <= n { // 퇴사 일 이후를 넘기지 않는지 확인
    dp[dur] = max(dp[dur], dp[i-1] + arr[i].1)
  }
}

print(dp.max()!)