문제 유형 중, DP의 추천문제들을 풀고 있습니다.
DP1의 문제양이 많아, DP1-1과 DP1-2로 나눕니다. (DP1-1은 여기서 확인할 수 있습니다.)
추천문제 번호 모음은 하단 링크에서 확인할 수 있습니다. 실버, 골드가 섞여있습니다.
https://github.com/tony9402/baekjoon/tree/main/dynamic_programming_1
GitHub - tony9402/baekjoon: 코딩테스트 대비 문제집(Baekjoon Online Judge)
코딩테스트 대비 문제집(Baekjoon Online Judge). Contribute to tony9402/baekjoon development by creating an account on GitHub.
github.com
문제 풀이를 할 때 마다 계속 추가됩니다.
cmd + F 를 통해 문제번호 찾기를 추천드립니다.
22.05.01 업데이트
22.05.02 업데이트
22.05.03 업데이트
22.05.04 업데이트
아래 깃허브 주소에서 모든 백준 문제풀이를 확인하실 수 있습니다.
https://github.com/SuminPark-developer/BaekJoonPS
GitHub - SuminPark-developer/BaekJoonPS: 백준 Swift PS
백준 Swift PS. Contribute to SuminPark-developer/BaekJoonPS development by creating an account on GitHub.
github.com
https://developer-p.tistory.com/201
DP(1-1) 문제 풀이 모음 | 백준 Swift 2748번, 11051번, 2839번, 1010번, 9655번, 17626번, 1463번, 9095번, 15988번,
문제 유형 중, DP의 추천문제들을 풀어보려고 합니다. (Dynamic Programming 1) DP1과 DP2 중 DP1부터 풀어나가겠습니다. (DP1의 문제양이 많아, DP1-1과 DP1-2로 나눕니다.) 추천문제 번호 모음은 여기서 확인
developer-p.tistory.com
백준 Swift 2294번
문제 유형 : DP(재귀, 반복문)
- 고민해서 풀었지만 틀렸다. 하단의 반례에서 바로 막혔다. 큰 coin부터 돌면서 target을 나눠주고 나뉠때의 count를 배열에 저장하고, 그 중 가장 작은 값을 출력하면 될 거라고 생각했기 때문이다. 최하단의 틀린코드에서 볼 수 있다.
다른 블로그를 참고해서 해결했다.
만약 막혀서 글을 찾아오게 된 거라면, dp배열을 0부터 ~ k까지 만들고, dp[0] = 0, 나머지 인덱스엔 10001을 넣고 다시 시도해보길 추천한다.
(왜 10001인가? 가능한 합인 k가 최대 10000이니까, 개수를 최대한으로 늘리고 싶으면 1원짜리로 만개를 만들면 된다. 즉, 문제풀이는 동전갯수를 최소한으로 하기 싶기 때문에 dp값의 최대를 100001으로 준다.)
TC 1번에서,
0원을 만들 땐 코인이 0개 필요하다. -> dp[0] = 0
"Coin이 1원"일 때
1원을 만들 땐 코인이 1개 필요하다. -> dp[1] = 1
2원을 만들 땐 코인이 2개 필요하다. -> dp[2] = dp[1] + 1
... dp[15] = dp[14] + 1 = 15가 될 것이다.
"Coin이 5원"일 때
5원을 만들 땐 코인이 1개 필요하다. 근데 이미 dp[5]에 5가 저장되어 있다. -> dp[5] = min(dp[5], dp[5 - coin] + 1) = 1
10원을 만들 땐 코인이 2개 필요하다. 근데 이미 dp[5]에 10이 저장되어 있다. -> dp[10] = min(dp[10], dp[10 - coin] + 1) = 2
... dp[15] = min(dp[15], dp[15 - coin] + 1) = min(15, dp[10] + 1) = min(15, 3) = 3
이런식으로 업데이트가 될 것이다.
점화식
dp[i] = min(dp[i], dp[i - coin] + 1)
주의해야 할 것은 i - coin이 범위를 벗어나면 error가 난다. 이는 따로 처리를 해줘야겠지?
난이도 : 실버1
반례
대표 반례
2 10
2
3
=> 5가 아니라 4가 나와야 함.
참고 링크 : https://sihyungyou.github.io/baekjoon-2294/ | https://t.ly/RriS
반복문
// MARK: - 2294번(DP - 반복문)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, k) = (input[0], input[1])
var coins: [Int] = []
for _ in 0..<n {
coins.append(Int(readLine()!)!)
}
coins.sort(by: <)
var dp: [Int] = [0] + Array(repeating: 10001, count: k) // k의 최대값이 10000이기 때문에. (최대한 개수가 많게 1원짜리로해도 dp값의 최대는 10000이기 때문에.)
for coin in coins {
for j in 1...k {
if j - coin < 0 { // dp의 인덱스를 벗어나면 패스.
continue
}
dp[j] = min(dp[j], dp[j - coin] + 1)
}
}
if dp[k] == 10001 {
print(-1)
}
else {
print(dp[k])
}틀린 코드
틀린 코드
// MARK: - 2294번(틀린 코드)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, k) = (input[0], input[1])
var coins: [Int] = []
for _ in 0..<n {
coins.append(Int(readLine()!)!)
}
coins.sort(by: >)
var possibleCase: [Int] = []
for i in 0..<n {
var target = k
var count: Int = 0
var isDivided: Bool = false // 나눠지는 case인지 구분.
for j in i..<n {
count += target / coins[j]
target = target % coins[j]
if target == 0 { // 이미 k가 됐으면 더 이상 돌아볼 필요 없음.
isDivided = true
break
}
}
if isDivided {
possibleCase.append(count)
}
}
var answer: Int? = possibleCase.min()
if answer == nil { // 만약 가능한 case가 없으면, -1을 출력.
print("-1")
}
else {
print(answer!)
}백준 Swift 11660번
문제 유형 : DP(재귀, 반복문)
- 백준 11659번을 먼저 풀기를 추천한다. (https://www.acmicpc.net/problem/11659 | https://www.acmicpc.net/board/view/17136)
11659번을 풀고 생각한다면, 하나의 행에서 (a ~ b)의 부분합은 S(b) - S(a-1)일 것이다.
하지만 이번엔 하나의 행이 아니다. 두가지의 단계를 거치면 된다.
(1,1) ~ (i, j)까지의 합을 구하는 dp배열을 우선 구한다.
| 0 | 0 | 0 |
| 0 | 1 | 3 |
| 0 | 3 | ? |
위는 dp배열의 일부이다. 예를 들어 (1,1) ~ (2,2)의 합은 무엇일까? 즉, dp[2][2]는 무엇인가?
빨간색과 파란색을 섞으면 보라색이 된다. 보라색은 중복되는 부분이란 소리다.
-> dp[2][2] = dp[2][1] + dp[1][2] - dp[1][1] + arr[2][2]이다.
dp배열의 점화식은 위와 같다.
dp배열을 구했으니, 이젠 답을 구해야 한다.
예를들어 (2, 2) ~ (3, 4)를 구해보자. 아래는 dp배열의 일부이다.
(2, 2) ~ (3, 4)의 구간합(흰색부분)을 구하기 위해선 어떻게 해야 할까? 위 그림을 참고하면 이해가 쉽다.
전체 D에서 A와 B를 빼주고, 중복으로 뺀 C를 더해주면 흰색부분(구간합)을 구할 수 있다.
즉, answer = dp[3][4] - dp[3][1] - dp[1][4] + dp[1][1] 이다.
이런식으로 점화식을 짜면 된다.
점화식
answer = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]
난이도 : 실버1
참고 자료 : https://chanhuiseok.github.io/posts/baek-19/
반복문
// MARK: - 11660번(DP - 반복문)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var arr: [[Int]] = Array(repeating: [], count: N + 1)
var dp = Array(repeating: Array(repeating: 0, count: N + 1), count: N + 1)
for _ in 0...N {
arr[0].append(0)
}
for i in 1...N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
arr[i] = [0] + input
}
for i in 1...N {
for j in 1...N {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i][j]
}
}
//print(dp)
for _ in 0..<M {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (x1, y1, x2, y2) = (input[0], input[1], input[2], input[3])
let answer = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]
print(answer)
}
백준 Swift 21317번
문제 유형 : DP(재귀, 반복문)
- 처음엔 푼게 맞은줄 알았다. 근데 아래에 반례를 넣어보니까 안됐다. 처음에 생각했던건 k를 한번만 쓰는거니까 check Bool을 두고, 경우를 나눠줬다.
왜 틀렸는지에 대해서 생각을 많이 했다. 생각해보니 TC1은 잘 되긴 하지만, N이 짧아서 가능했다. 즉, N이 길어질수록 k가 쓰였을 때의 최소가 되는 값을 알 수 없게 되게 짜서 틀렸다.
dp[i][j]에서,
j == 0 : k를 사용하지 않은 경우.
j == 1 : k를 사용한 경우.
최소값을 구해야 하는 문제고, 에너지의 최대가 5000이기 때문에 5001을 기본적으로 저장한다. (지금 작성하면서 생각해보니 5001이 아니라, Int의 최대값과 인접한 값을 넣는게 맞는 것 같다. 잘못하면 dp[4][1]의 값에서 문제가 생기는 케이스가 발생할 수 있는 거 같다.)
1번 돌은 시작점이기 때문에 dp값이 0이다.
[0]에 대해 생각해보자. (k를 쓰지 않을 때)
2번 돌은 1번돌에서 smallJ일 때만 가능하기 때문에, dp[2][0] = smallJ[1]이다.
3번 돌은 1번돌에서 bigJ 혹은 2번돌에서 smallJ가 가능하기 때문에, dp[3][0] = min(dp[1][0] + bigJ[1], dp[2][0] + smallJ[2])이다.
즉, [0]의 점화식은 dp[i][0] = min(dp[i - 1][0] + smallJ[i - 1], dp[i - 2][0] + bigJ[i - 2]) 다.
4번 돌부터 매우 큰 점프 k를 쓸 수 있다. [0]은 계속 위와 같은 방식이고, [1]에 대해 생각해보자. (k를 쓸 때)
1번째 돌에서 k를 써서 오는 경우 or 2번째 돌에서 bigJ를 써서 오는 경우 or 3번째 돌에서 smallJ를 써서 오는 경우가 있을 것이다.
즉, [1]의 점화식은 dp[i][1] = min(dp[i - 3][0] + k, dp[i - 2][1] + bigJ[i - 2], dp[i - 1][1] + smallJ[i - 1]) 다.
난이도 : 실버1
참고 자료 : https://blog.naver.com/PostView.nhn?blogId=gustn3964&logNo=222303877311
반례
6
1 2
2 3
4 5
6 7
8 10
4반복문
// MARK: - 21317번(DP - 반복문)
let N = Int(readLine()!)!
var smallJ: [Int] = [0] + Array(repeating: 0, count: N - 1)
var bigJ: [Int] = [0] + Array(repeating: 0, count: N - 1)
var dp: [[Int]] = Array(repeating: Array(repeating: 5001, count: 2), count: N + 1)
dp[0][0] = 0
dp[0][1] = 0
dp[1][0] = 0
dp[1][1] = 0
for i in 1..<N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (smallEnergy, bigEnergy) = (input[0], input[1])
smallJ[i] = smallEnergy
bigJ[i] = bigEnergy
}
let k: Int = Int(readLine()!)!
if N == 2 {
dp[2][0] = smallJ[1]
}
else if N == 3 {
dp[2][0] = smallJ[1]
dp[3][0] = min(dp[2][0] + smallJ[2], bigJ[1])
}
else if N >= 4 {
dp[2][0] = smallJ[1]
dp[3][0] = min(dp[2][0] + smallJ[2], bigJ[1])
for i in 4...N {
dp[i][0] = min(dp[i - 1][0] + smallJ[i - 1], dp[i - 2][0] + bigJ[i - 2]) // k를 사용하지 않을 때.
dp[i][1] = min((dp[i - 3][0] + k), (dp[i - 1][1] + smallJ[i - 1]), (dp[i - 2][1] + bigJ[i - 2])) // k를 사용할 때.
}
}
//print(dp)
print(dp[N].min()!)틀린코드
// MARK: - 21317번(DP - 반복문: 틀린코드)
let N = Int(readLine()!)!
var smallJ: [Int] = [0] + Array(repeating: 0, count: N - 1)
var bigJ: [Int] = [0] + Array(repeating: 0, count: N - 1)
var dp: [Int] = [0] + Array(repeating: 0, count: N)
for i in 1..<N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (smallEnergy, bigEnergy) = (input[0], input[1])
smallJ[i] = smallEnergy
bigJ[i] = bigEnergy
}
let k: Int = Int(readLine()!)!
if N == 2 {
dp[2] = smallJ[1]
}
else if N == 3 {
dp[2] = smallJ[1]
dp[3] = min(dp[2] + smallJ[2], bigJ[1])
}
else if N >= 4 {
dp[2] = smallJ[1]
dp[3] = min(dp[2] + smallJ[2], bigJ[1])
var useK: Bool = false // k를 썼는지 체크.
for i in 4...N {
if !useK { // k를 아직 쓰지 않았을 때,
var minTemp = min((dp[i - 1] + smallJ[i - 1]), (dp[i - 2] + bigJ[i - 2])) // 잠시 저장.(k를 쓸 때가 가장 작은지 확인하기 위해.)
if dp[i - 3] + k < minTemp { // k를 쓴게 더 작으면,
minTemp = dp[i - 3] + k
useK = true // k 사용.
}
dp[i] = minTemp
}
else { // k를 이미 사용한 상태라면,
dp[i] = min((dp[i - 1] + smallJ[i - 1]), (dp[i - 2] + bigJ[i - 2]))
}
}
}
//print(dp)
print(dp[N])백준 Swift 22869번
문제 유형 : DP(재귀, 반복문)
- 풀이를 알고 보면 매우 간단하다. 대부분의 문제가 그렇긴 하겠지만...
최단경로가 아니라, 갈 수 있는지 없는지만 알면 된다. dp배열을 (boolean)배열로 놓고, true일 때만 확인해주면 된다. (난 true/false = 1/0로 했다.)
그리고 매 반복문마다 dp[N] == 1인지 체크해서, 1이라면 더 알아볼 필요도 없이 YES하고 break를 하면 시간을 조금 더 단축시킬 수 있다.
난이도 : 실버1
반복문
// MARK: - 22869번(DP - 반복문)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, K) = (input[0], input[1])
var arr: [Int] = [0] + readLine()!.split(separator: " ").map{Int(String($0))!}
var dp: [Int] = [0] + Array(repeating: 0, count: N)
dp[1] = 1 // 첫번째 돌은 이동가능이라 1로 표시.
var answer: String = "NO"
for i in 1..<N { // 첫번째 돌부터,
if dp[i] == 1 { // 이동 가능한 곳만 체크.
for j in i+1...N {
let power = (j - i) * (1 + abs(arr[i] - arr[j]))
if power <= K { // 이동가능하다면,
dp[j] = 1 // 이동가능한곳 1로 표시.
}
}
if dp[N] == 1 {
answer = "YES"
break
}
}
}
print(answer)틀린 고민
문제 유형 : DP(재귀, 반복문)
- 처음에 얼추 비슷하게 접근은 했는데 구현을 잘 못했다.
dp배열은 i명까지 만드는데 드는 비용을 저장한다. 근데 문제에서 물어보는게 적어도 C명일 때의 최소비용이기 때문에, dp[C]가 아니다!
적어도 C명이라는건 C명 이상이란 뜻이기도 하고, C를 넘기면서 최소인 상황이 존재하기 때문이다.
이해가 되는가? 따라서 dp[C] ~ dp[C+100] 중에서 최소값이다.
비용과 고객 수는 최대 100이다. 값은 Int.max - 100을 해줘야 계산이 error가 안나고, 길이는 C + 100을 해줘야 한다.
좀 더 자세한 내용은 아래 풀이에서 확인할 수 있다.
var dp: [Int] = [0] + Array(repeating: Int.max - 100, count: C + 100) // 비용이 최대 100이기 때문에, 최대값 - 100을 해줘야 계산이 가능해진다.
난이도 : 골드5
참고 자료 : https://dirmathfl.tistory.com/379
반복문
// MARK: - 1106번(DP - 반복문)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (C, N) = (input[0], input[1])
var ad: [(cost: Int, customer: Int)] = [(0, 0)]
for _ in 0..<N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
ad.append((input[0], input[1]))
}
var dp: [Int] = [0] + Array(repeating: Int.max - 100, count: C + 100) // 비용이 최대 100이기 때문에, 최대값 - 100을 해줘야 계산이 가능해진다.
//var dp: [Int] = [0] + Array(repeating: 10000, count: C + 100)
for (cost, customer) in ad {
for i in customer...(C+100) {
dp[i] = min(dp[i], dp[i - customer] + cost)
}
}
let answer = dp[C...C+100].min()! // C ~ C+100명 늘이는 것 중 돈의 최소값.
print(answer)
백준 Swift 2293번
문제 유형 : DP(재귀, 반복문)
- 쭉 나열해봤는데 모르겠었다.
핵심은 새로운 coin이 나타나면서 생길 수 있는 경우의 수를 기존의 dp값에 더해주는 게 핵심이다.
내 힘으로 푼 게 아니라서 다음에 다시 풀어봐야겠다.
(매우 유사한) 백준 9084번을 다시 풀었다. (풀이 : https://developer-p.tistory.com/205) - 22.05.12 업데이트
백준 2293번 컴파일 에러나는 이유 2가지
1. 동전의 가치(coin)이 가치들의 합(k)보다 큰 케이스가 있으니, 예외처리를 해줘야 한다.
2. 경우의 수가 2^31을 벗어나는 케이스가 있으니, 예외처리를 해줘야 한다.
3. (Swift만 해당) - 나처럼 바보같이 import Foundation을 빼먹고 작성하면...안된다!
pow를 썼는데 어떻게 에러가 뜬 걸 모를 수 있지? 라고 의문이 들 수 있다.
작성하던 코드 위쪽에 import Darwin이 있어서 에러가 안나서 몰랐다. (https://stackoverflow.com/questions/24012511/mathematical-functions-in-swift)
난이도 : 골드5
반례
반례
1 10000
100000
참고 자료 : https://seongonion.tistory.com/108 | https://www.acmicpc.net/board/view/27103
반복문
// MARK: - 2293번(DP - 반복문)
import Foundation // pow에 쓰임.
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, k) = (input[0], input[1])
var coins: [Int] = []
for _ in 0..<n {
coins.append(Int(readLine()!)!)
}
var dp: [Int] = [1] + Array(repeating: 0, count: k) // dp[0] = 1
for coin in coins {
if coin > k { // 동전의 가치가 합k보다 클 때, 에러를 방지하기 위해.
continue
}
for i in coin...k {
if dp[i] + dp[i - coin] > Int(pow(2.0, 31.0)) { // 경우의 수가 2^31을 벗어나는 경우, 에러를 방지하기 위해.
dp[i] = 0
}
else {
dp[i] = dp[i] + dp[i - coin]
}
}
}
print(dp[k])
최근댓글