문제 유형 중, DP의 추천문제들을 풀어보려고 합니다. (Dynamic Programming 1)
DP1과 DP2 중 DP1부터 풀어나가겠습니다. (DP1의 문제양이 많아, DP1-1과 DP1-2로 나눕니다.)
추천문제 번호 모음은 여기서 확인할 수 있습니다. 브론즈, 실버, 골드가 섞여있습니다.
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.04.15업데이트
22.04.16 업데이트
22.04.17 업데이트
22.04.18 업데이트
22.04.19 업데이트
22.04.22 업데이트
22.04.23 업데이트
22.04.25 업데이트
22.04.26 업데이트
22.04.28 업데이트
22.04.29 업데이트
22.04.30 업데이트
아래 깃허브 주소에서 모든 백준 문제풀이를 확인하실 수 있습니다.
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/203
DP(1-2) 문제 풀이 모음 | 백준 Swift 2294번, 11660번, 21317번, 22869번, 1106번, 2293번
백준 Swift 2293번 Eng 백준 Swift 2293번 {"mean":[" swift 미국∙영국[swɪft] (일진행 등이) 신속한[재빠른] (움직임이) 빠른[날랜] 칼새 "," 번 (횟수, 차례, 경우) time, occasion; (시도) try (번호) number..
developer-p.tistory.com
백준 Swift 2748번
문제 유형 : DP(재귀, 반복문)
난이도 : 브론즈1
DP - 재귀
// MARK: - 2748번(DP - 탑다운)
let n = Int(readLine()!)!
var cache = Array(repeating: -1, count: 91)
cache[0] = 0
cache[1] = 1
func fibo(_ num: Int) -> Int {
if cache[num] == -1 {
cache[num] = fibo(num - 1) + fibo(num - 2)
}
return cache[num]
}
let answer = fibo(n)
print(answer)DP - 반복문
// MARK: - 2748번(DP - 바텀업)
let n = Int(readLine()!)!
var cache = Array(repeating: -1, count: n + 1)
cache[0] = 0
cache[1] = 1
if n >= 2 {
for i in 2...n {
cache[i] = cache[i - 1] + cache[i - 2]
}
}
print(cache[n])
//var numArray = [0, 1]
//
//func fibo(_ num: Int) -> Int {
// if num >= 2 {
// for i in 2...n {
// numArray.append(numArray[i-1] + numArray[i-2])
// }
// }
// return numArray[num]
//}
//print(fibo(n))백준 Swift 11051번
문제 유형 : DP(재귀, 반복문)
- DP문제들을 처음 접해보는데, 점화식을 알아내서 세우는 게 어려운 것 같다.
난이도 : 실버1
재귀
// MARK: - 11051번(DP - 재귀함수)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, K) = (input[0], input[1])
var cache = Array(repeating: Array(repeating: -1, count: K + 1), count: N + 1)
func bino(_ n: Int, _ k: Int) -> Int {
if cache[n][k] != -1 {
return cache[n][k]
}
if k == 0 || k == n {
cache[n][k] = 1
}
else {
cache[n][k] = (bino(n - 1, k - 1) + bino(n - 1, k)) % 10007 // 나중에 answer에서 mod를 해주면 안됨.(그러면 Int범위 초과)
}
return cache[n][k]
}
let answer = bino(N, K)
print(answer)반복문
// MARK: - 11051번(DP - 반복문)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, K) = (input[0], input[1])
var cache = Array(repeating: Array(repeating: -1, count: K + 1), count: N + 1)
for j in 1...N {
for i in 0...K {
if i == 0 || i == j {
cache[j][i] = 1
}
else {
cache[j][i] = (cache[j - 1][i - 1] + cache[j - 1][i]) % 10007 // 나중에 mod해주면 Int범위 초과.
}
}
}
print(cache[N][K])
백준 Swift 2839번
문제 유형 : DP(재귀, 반복문)
재귀 - 생각 못했다. 그리디로 풀면 풀 수 있을 거 같은데, 재귀로 풀려니까 어려웠다. 분기 조건을 눈치채야 하는데... 쭉 써 봤는데 그래도 알아내는 게 어려운 것 같다.
반복문 - 재귀로 풀고 나서 해서 그런지, 쉽게 풀었다. 재귀함수 다루는 걸 어려워 하는 것도 한 몫 하는 것 같다. 얼른 익숙해지도록 노력해야겠다.
swift는 for문을 돌릴 때, for문의 범위를 벗어나는 N이 들어오면 Error가 뜬다. 그래서 for문 밖에 if문을 넣어서 해결하면 된다. (파이썬은 에러없이 알아서 패스해주던데...)
난이도 : 골드5
참고 링크 : https://velog.io/@hye0n/BOJPython-2839.%EC%84%A4%ED%83%95-%EB%B0%B0%EB%8B%AC
재귀
// MARK: - 2839번(DP - 재귀함수)
let N = Int(readLine()!)!
var cache = Array(repeating: -1, count: 5001)
(cache[3], cache[5]) = (1, 1)
func topDown(_ num: Int) -> Int {
if num <= 0 { // topDown(num-5) 때문에 인덱스를 벗어나게 되면 -1을 리턴.
return -1
}
if cache[num] != -1 { // 결과값이 있다면, 더 돌아볼 필요 없이 결과값 리턴.
return cache[num]
}
if num % 5 == 0 { // 5의 배수일 때,
cache[num] = topDown(num - 5) + 1 // 현재num의 결과값 = 이전 5의배수의 결과값 + 1
}
else if num % 3 == 0 { // 3의 배수일 때,
cache[num] = topDown(num - 3) + 1 // 현재num의 결과값 = 이전 3의배수의 결과값 + 1
}
else if topDown(num - 5) != -1 { // 이전(num-5)가 값이 있다면,
cache[num] = topDown(num - 5) + 1 // 현재num의 결과값 = 이전 결과값 + 1
}
else if topDown(num - 3) != -1 { // 이전(num-3)가 값이 있다면,
cache[num] = topDown(num - 3) + 1 // 현재num의 결과값 = 이전 결과값 + 1
}
// else {
// cache[num] = -1
// }
return cache[num]
}
print(topDown(N))반복문
// MARK: - 2839번(DP - 반복문)
let N = Int(readLine()!)!
var cache = Array(repeating: -1, count: 5001)
cache[3] = 1
if N >= 5 { // i - 5를 체크할 때 인덱스를 벗어나는걸 방지하기 위해, N >= 5 부터 for문 시작.
for i in 5...N {
if i % 5 == 0 { // 5로 나뉘면,
cache[i] = i / 5
}
else if i % 3 == 0 { // 3으로 나뉘면,
cache[i] = cache[i - 3] + 1 // 이전 결과값 + 1
}
else if (cache[i - 5] != -1) { // 이전(i-5)이 값이 있다면,
cache[i] = cache[i - 5] + 1 // 현재 결과값 = 이전 결과값 + 1
}
else if (cache[i - 3] != -1) { // 이전(i-3)이 값이 있다면,
cache[i] = cache[i - 3] + 1 // 현재 결과값 = 이전 결과값 + 1
}
}
}
print(cache[N])
백준 Swift 1010번
문제 유형 : DP(재귀, 반복문)
재귀 - 오로지 내 힘으로 풀었다! 아까 이항 계수(파스칼의 삼각형) 공식을 배워놔서, 풀 수 있었다. (백준 11051번)
DP문제를 풀 때 자주 나온다고 하니 잊지 않도록 해야겠다.
반복문 - 역시 재귀와 마찬가지로, 이항계수 점화식을 활용해 풀 수 있었다.
이항계수 조건 및 점화식
bino(n, 0) = 1
bino(n, n) = 1
bino(n, r) = bino(n-1, r-1) + bino(n-1, r)
난이도 : 실버5
재귀
// MARK: - 1010번(DP - topDown)
let T = Int(readLine()!)!
for _ in 0..<T {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var cache = Array(repeating: Array(repeating: -1, count: 30), count: 30)
func bino(_ m: Int, _ n: Int) -> Int { // 이항계수
if cache[m][n] != -1 {
return cache[m][n]
}
if n == 0 || n == m { // mC0 이나 mCm일 때,
cache[m][n] = 1
}
else { // n이 1 ~ m-1일 땐,
cache[m][n] = bino(m - 1, n - 1) + bino(m - 1, n)
}
return cache[m][n]
}
let answer = bino(M, N)
print(answer)
}반복문
// MARK: - 1010번(DP - bottomUp)
let T = Int(readLine()!)!
for _ in 0..<T {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
//
// var cache = Array(repeating: Array(repeating: -1, count: N + 1), count: M + 1)
//
// for i in 1...M {
// for j in 0...N {
// if j == 0 || j == i {
// cache[i][j] = 1
// }
// else {
// cache[i][j] = cache[i - 1][j - 1] + cache[i - 1][j]
// }
// }
// }
var cache = Array(repeating: Array(repeating: -1, count: 30), count: 30)
for i in 1..<30 {
cache[i][i] = 1
cache[i][0] = 1
for j in 1..<i {
cache[i][j] = cache[i - 1][j - 1] + cache[i - 1][j]
}
}
print(cache[M][N])
}
백준 Swift 9655번
문제 유형 : DP(재귀, 반복문)
- 이 문제는 DP가 아니라, 그냥 쭉 써보고 홀수&짝수로 나누면 풀리는 문제였다.(3번째 코드)
하지만 DP로 분류가 되어 있으니까 DP로도 풀어보려 했는데, 잘 안됐다.
고민하다가 다른 블로그들을 참고했다.
재귀가 익숙치 않아서 그런지, 문제를 풀 때 반복문이 더 쉬운 것 같다.
앞으론 DP문제를 접근할 때 반복문으로 먼저 접근을 하고, 재귀로 재접근을 하는 식으로 푸는 게 나을 것 같다.
(알고리즘 코테 강의에선 재귀가 더 쉽다고 했는데... 난이도 느끼는건 사람마다 다른 거니깐...)
BottomUp(반복문)은 n-3과 n-1의 결과값을 계속 끌고 올라가면 된다.
주의해야 할 건, n-3이 있기 때문에, cache에 인덱스1, 2, 3의 값은 저장해놓고, n을 4부터 반복문을 돌린다.
TopDown(재귀)은 주어진 n값에서, n-3과 n-1의 값을 반복해서 호출하면 된다.
반복문과 마찬가지로, 인덱스 1, 2, 3의 값은 예외처리 해주고,
추가적으로 cache[n] 값이 -1이 아닐 땐 방문한 적이 있다(=값이 저장되어 있다.)는 뜻이므로, 바로 값을 리턴해준다.
난이도 : 실버5
참고 링크 : https://beginnerdeveloper-lit.tistory.com/83 | https://propercoding.tistory.com/21
재귀
// MARK: - 9655번(DP - 재귀함수)
let N = Int(readLine()!)!
var cache = Array(repeating: -1, count: 1001)
func topDown(_ n: Int) -> Int {
if cache[n] != -1 { // 기록된 적 있으면, 더 확인할 필요 없이 저장된 값을 리턴.
return cache[n]
}
if n == 3 || n == 1 { // n이 1이나 3일 땐, 게임횟수 1.
cache[n] = 1
}
else if n == 2 { // n이 2일 땐, 게임횟수 2.
cache[n] = 2
}
else { // n이 4이상일 땐, 이전 기록(n-3, n-1) 중 작은것 + 1
cache[n] = min(topDown(n - 3), topDown(n - 1)) + 1
}
return cache[n]
}
if topDown(N) % 2 == 1 { // 게임횟수가 홀수면,
print("SK")
}
else { // 게임횟수가 짝수면,
print("CY")
}반복문
// MARK: - 9655번(DP - 반복문)
let N = Int(readLine()!)!
var cache = Array(repeating: -1, count: 1001) // 게임 과정 기록.
cache[2] = 2
cache[3] = 1
if N >= 4 {
for i in 4...N {
cache[i] = min(cache[i - 3], cache[i - 1]) + 1
}
}
if cache[N] % 2 == 1 { // 게임한 횟수가 홀수면,
print("SK")
}
else { // 게임한 횟수가 짝수면,
print("CY")
}그냥 풀이
// MARK: - 9655번(그냥 풀이)
let N = Int(readLine()!)!
if N % 2 == 1 {
print("SK")
}
else {
print("CY")
}백준 Swift 17626번
문제 유형 : DP(재귀, 반복문)
쭉 써봐도 규칙을 못찾겠었다. 결국엔 다른 블로그를 참고해서 이해했다. 점화식을 구하는 게 핵심인데, 아직 어려운 것 같다.
주의사항은, i보다 이전 숫자 중, 가장 큰 제곱수의 결과값 + 1이 답이 아니다.
반례 : 12일 때 dp[3^2] + 1을 하면 4인데, 실제론 2^2 + 2^2 + 2^2 해서 3이 나와야 한다.
재귀함수로 푼 코드는 없는 거 같아서, 시도해봤는데 Xcode에서 시간초과가 난다.
혹시나 몰라서 백준에 제출해보니 백준에선 통과가 됐다. 아마 depth가 깊어지면서 xcode에선 막는 것 같다.
어떻게 수정해야 하는진 모르겠는데, 아시는 분은 댓글로 꼭 알려주세요! (https://www.acmicpc.net/board/view/88588)
난이도 : 실버4
참고 링크 : https://loosie.tistory.com/229
재귀
// MARK: - 17626번(DP - 재귀함수) - 시간초과
let n = Int(readLine()!)!
var cache = Array(repeating: -1, count: n + 1)
//cache[0] = 0
//cache[1] = 1
func topDown(_ num: Int) -> Int {
if cache[num] != -1 {
return cache[num]
}
if num == 0 || num == 1 {
cache[num] = num
}
else {
var minValue = 50001
var i = 1
while i * i <= num {
minValue = min(minValue, topDown(num - i * i))
i += 1
}
cache[num] = minValue + 1
}
return cache[num]
}
print(topDown(n))반복문
// MARK: - 17626번(DP - 반복문)
let n = Int(readLine()!)!
var cache = Array(repeating: -1, count: n + 1)
cache[0] = 0
cache[1] = 1
if n >= 2 {
for i in 2...n {
var minValue = 50001
var j = 1
while j * j <= i { // 제곱했을 때 i의 범위를 벗어나지 않을 때,
minValue = min(minValue, cache[i - j * j]) // i보다 작은, 가능한 제곱수들 중 가장 작은 값으로. 가능한 최소여야 하기 때문.
j += 1
}
cache[i] = minValue + 1 // 값 + 1을 해줘야 해당 결과값이 나옴.
// print(cache)
}
}
print(cache[n])
백준 Swift 1463번
문제 유형 : DP(재귀, 반복문)
쭉 작성하다 보니까 규칙이 보였다. 처음엔 3이나 2로 나뉘면, 그 값 + 1이 결과값이라고 생각했다. 아니다!
하단 이미지의 dp[10]을 보면 알겠지만, 10에서 -1연산을 하고, 3으로 나눠주는 연산을 하는게 최소다.
즉, 3으로 나뉠 때, min(dp [i / 3], dp[i - 1]) + 1이다.
2로 나뉠때도 마찬가지로, min(dp [i / 2], dp[i - 1]) + 1이다.
이렇게 코드를 짜고 틀렸다. 왜 틀렸을까?
주의해야 할 것은, 3과 2가 동시에 나뉘는 6의 배수일 때다.
3과 2로 나뉘는 수일 땐, dp[i/3] 값과 dp[i/2]값 중 작은 값으로 계산을 해줘야 한다. +1은 당연히 해줘야 하고.
반례는 642다. (정답: 10, 오답: 11) 6의 배수를 고려하지 않았던 첫 코드는 오답이 나온다. (대표 반례 : https://www.acmicpc.net/board/view/49959)
재귀함수 코드보다, 반복문 코드를 먼저 보고 이해하기를 추천한다. (개인적으론 그게 더 쉽다..)
난이도 : 골드5
재귀
// MARK: - 1463번(DP - 재귀함수)
let N = Int(readLine()!)!
var cache = Array(repeating: -1, count: 1000001)
func topDown(_ n: Int) -> Int {
if cache[n] != -1 {
return cache[n]
}
if n <= 0 {
return -1
}
if n <= 3 { // 3이하일 땐, 기본값 세팅.
cache[1] = 0
cache[2] = 1
cache[3] = 1
}
else { // 4이상일 땐,
if n % 6 == 0 {
cache[n] = min(topDown(n / 3), topDown(n / 2), topDown(n - 1)) + 1
}
else if n % 3 == 0 {
cache[n] = min(topDown(n / 3), topDown(n - 1)) + 1
}
else if n % 2 == 0 {
cache[n] = min(topDown(n / 2), topDown(n - 1)) + 1
}
else {
cache[n] = topDown(n - 1) + 1
}
}
return cache[n]
}
let answer = topDown(N)
print(answer)반복문
// MARK: - 1463번(DP - 반복문)
let N = Int(readLine()!)!
var cache = Array(repeating: -1, count: 1000001)
cache[1] = 0
cache[2] = 1
cache[3] = 1
if N >= 4 {
for i in 4...N {
if i % 3 == 0 && i % 2 == 0 { // 6의 배수일 때 -> (/3 연산, /2 연산, -1연산) 중 작은 값 + 1
cache[i] = min(cache[i / 3], cache[i / 2], cache[i - 1]) + 1
}
else if i % 3 == 0 { // 3의 배수일 때 -> (/3 연산, -1연산) 중 작은 값 + 1
cache[i] = min(cache[i / 3], cache[i - 1]) + 1
}
else if i % 2 == 0 { // 2의 배수일 때 -> (/2 연산, -1연산) 중 작은 값 + 1
cache[i] = min(cache[i / 2], cache[i - 1]) + 1
}
else { // 다 해당되지 않으면, -1연산 값 + 1
cache[i] = cache[i - 1] + 1
}
}
}
print(cache[N])
백준 Swift 9095번, 15988번
문제 유형 : DP(재귀, 반복문)
9095번을 먼저 푸는 걸 추천한다.
탑다운dp보다 바텀업dp를 권장한다고 한다. (참고 : https://www.acmicpc.net/board/view/70869)
쭉 적어봤을 때 규칙을 찾으려 했는데 못 찾았다. 고민하다 결국 다른 블로그를 참고했다.
그렇게 나온 점화식은 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]이다.
15988번을 기존에 썼던 코드를 확인 안하고 그대로 넣었더니 틀렸다. 매우 당황스러웠는데, 그 이유는 3가지였다. 틀린 이유 3이 제일 중요하다.
틀린 이유 1. cache범위를 늘리지 않았다.
틀린 이유 2. 문제에 주어진 수(1000000009)로 나누지 않았다.
틀린 이유 3. 시간초과가 나서 생각해보니, 9095번처럼 코드를 짜면 안됐다. 그렇게 하면 매 n마다, cache값을 다시 구하기 때문이다. (이미 값을 구한 적이 있음에도 불구하고.)
그래서 모든 값을 먼저 구해서 저장해놓고, 그 다음 결과값만 호출하는 식으로 수정해서 해결했다.
난이도 : 실버3, 실버2
참고 링크 : https://blog.naver.com/PostView.nhn?blogId=vjhh0712v&logNo=221470862600
9095번
재귀
// MARK: - 9095번(DP - 재귀함수)
let T = Int(readLine()!)!
var cache = Array(repeating: -1, count: 11)
for _ in 0..<T {
let n = Int(readLine()!)!
let answer = topDown(n)
print(answer)
}
func topDown(_ N: Int) -> Int {
if cache[N] != -1 {
return cache[N]
}
if N <= 3 {
cache[1] = 1
cache[2] = 2
cache[3] = 4
}
else {
cache[N] = topDown(N - 1) + topDown(N - 2) + topDown(N - 3)
}
return cache[N]
}반복문
// MARK: - 9095번(DP - 반복문)
let T = Int(readLine()!)!
var cache = Array(repeating: -1, count: 11)
cache[1] = 1
cache[2] = 2
cache[3] = 4
for _ in 0..<T {
let n = Int(readLine()!)!
if n >= 4 { // 4부터 점화식 성립.
for i in 4...n {
cache[i] = cache[i - 1] + cache[i - 2] + cache[i - 3]
}
}
print(cache[n])
}15988번
재귀
// MARK: - 15988번(DP - 재귀함수) : Xcode에선 에러
let T = Int(readLine()!)!
var cache = Array(repeating: -1, count: 1000001)
func topDown(_ N: Int) -> Int {
if cache[N] != -1 {
return cache[N]
}
if N <= 3 {
cache[1] = 1
cache[2] = 2
cache[3] = 4
}
else {
cache[N] = (topDown(N - 1) + topDown(N - 2) + topDown(N - 3)) % 1000000009
}
return cache[N]
}
for _ in 0..<T {
let n = Int(readLine()!)!
let answer = topDown(n)
print(answer)
}반복문
// MARK: - 15988번(DP - 반복문)
let T = Int(readLine()!)!
var cache = Array(repeating: -1, count: 1000001)
cache[1] = 1
cache[2] = 2
cache[3] = 4
for i in 4...1000000 { // 4부터 점화식 성립.
cache[i] = (cache[i - 1] + cache[i - 2] + cache[i - 3]) % 1000000009
}
for _ in 0..<T {
let n = Int(readLine()!)!
print(cache[n])
}
백준 Swift 11726번
문제 유형 : DP(재귀, 반복문)
어렵지 않게 풀 수 있었다. DP문제는 쭉 나열하면서 표를 그린 뒤, 점화식을 구하는 게 핵심인 것 같다. 점화식을 구하는 게 어려워서 그렇지...
아래 그림을 보면, 직사각형이 어떻게 채워지고 갯수는 몇 개가 나오는지 알 수 있다.
난이도 : 실버3
재귀
// MARK: - 11726번(DP - 재귀함수)
let n = Int(readLine()!)!
var cache = Array(repeating: -1, count: 1001)
func topDown(_ N: Int) -> Int {
if cache[N] != -1 {
return cache[N]
}
if N <= 2 {
cache[N] = N
}
else {
cache[N] = (topDown(N - 1) + topDown(N - 2)) % 10007
}
return cache[N]
}
print(topDown(n))반복문
// MARK: - 11726번(DP - 반복문)
let n = Int(readLine()!)!
var cache = Array(repeating: -1, count: 1001)
cache[1] = 1
cache[2] = 2
if n >= 3 {
for i in 3...n {
cache[i] = (cache[i - 1] + cache[i - 2]) % 10007
}
}
print(cache[n])
DP
data processing, degree of polymerization [화학] 중합도(重合度), [야구] designated player, dew point, displaced person, doctor of pharmacy, double play
dp
data processing, [야구] double play
D/P
상업 documents against payment.
D.P.
의학 적당(適當)한 지시(指示)대로, L. directione propria의 약자.
의학 약학박사(藥學博士) Doctor of Pharmacy의 약자.
의학 수족치료의사(手足治療醫師). Doctor of Podiatry의 약자.
drop point
군사 투하지점
오픈
예제
The DP has been aggressively promoting its campaign.
민주당은 이 무상급식 캠페인을 강력하게 추진해왔다.
We think some events should be held in North Korea,' said Sohn Kak-kyu, chairman of the DP.'
일부 경기는 북한에서 개최되어야 한다고 생각한다.'
DP lawmakers then used a sledgehammer and crowbars to break down the door to the meeting room.
그러자 민주당 국회의원들은 쇠망치와 쇠지레를 사용해 회의실 문을 부수었다.
They hoped to keep DP lawmakers from participating in the process.
이들은 민주당 의원들이 이 절차에 참여하는 것을 막기를 원했다.
The DP criticized him more specifically for behavior they call unethical.
민주당은 비윤리적인 행동에 대해 명확히 비판하였다.
VLIVE 자막
What is "DP"? "DP"?
플꾸가 뭐야? 폴꾸?
What is "DP"?
폴꾸가 뭐예요?
"DP"? - What does that mean?
폴꾸? - 무슨 소리지?
What is that? - Don't you know DP?
그게 뭐예요? - 폴꾸, 그것도 몰라요?
What are you doing? - Do you know DP?
뭐 하는 거예요? - 폴꾸라고 아세요?
백준 Swift 2579번
문제 유형 : DP(재귀, 반복문)
생각 못했다. 다른 블로그를 참고해서 풀었다. 1일때부터 어떤 규칙인걸까 생각했는데, n을 기준으로 생각하니까 바로 나오더라.
case가 2가지로 나뉜다.
제일 마지막칸인 n을 기준으로,
case1. 직전칸 O : dp[n] = dp[n-3] + arr[n-1] + arr[n]
가장 마지막칸(n)은 반드시 방문해야 하고, 그 직전칸(n-1)에 방문한다면, n-2칸은 방문하지 못한다. (문제 조건 2에 의해)
그럼 n-3칸은 반드시 방문해야 하기 때문에, dp[n-3]값에 직전칸값(arr[n-1])과 마지막칸값(arr[n])을 더해주면 점화식이 나온다.
case2. 직전칸 X : dp[n] = dp[n-2] + arr[n]
직전칸(n-1)은 방문하지 않으므로, n-2칸은 반드시 방문해야 한다. 따라서 dp[n-2]값과 마지막칸값(arr[n])을 더해주면 점화식이 나온다.
case1과 case2 결과값 중 최대값을 dp[n]에 넣어주면 된다.
=> max((dp[n] = dp[n-3] + arr[n-1] + arr[n]), (dp[n] = dp[n-2] + arr[n]))
난이도 : 실버3
재귀
// MARK: - 2579번(DP - 재귀문)
let T = Int(readLine()!)!
var stairs = Array(repeating: 0, count: 301)
for i in 1...T {
let input = Int(readLine()!)!
stairs[i] = input
}
var cache = Array(repeating: -1, count: 301)
func topDown(_ N: Int) -> Int {
if cache[N] != -1 {
return cache[N]
}
if N <= 3 {
cache[1] = stairs[1]
cache[2] = stairs[1] + stairs[2]
cache[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])
}
else {
cache[N] = max(topDown(N - 3) + stairs[N - 1] + stairs[N], topDown(N - 2) + stairs[N])
}
return cache[N]
}
let answer = topDown(T)
print(answer)반복문
// MARK: - 2579번(DP - 반복문)
let T = Int(readLine()!)!
var stairs = Array(repeating: 0, count: 301)
for i in 1...T {
let input = Int(readLine()!)!
stairs[i] = input
}
var cache = Array(repeating: -1, count: 301)
cache[1] = stairs[1]
cache[2] = stairs[1] + stairs[2]
cache[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])
if T >= 4 {
for i in 4...T {
cache[i] = max((cache[i - 3] + stairs[i - 1] + stairs[i]), (cache[i - 2] + stairs[i]))
}
}
print(cache[T])
백준 Swift 11727번
문제 유형 : DP(재귀, 반복문)
쭉 나열해보면 규칙이 금방 보이는 문제다. n이 4일때까지 쭉 나열한다면 대부분 점화식을 구할 수 있을 것이다.
=> dp[n] = (2 * dp[n-2]) + dp[n-1]
난이도 : 실버3
재귀
// MARK: - 11727번(DP - 재귀)
let n = Int(readLine()!)!
var cache = Array(repeating: -1, count: 1001)
func topDown(_ N: Int) -> Int {
if cache[N] != -1 {
return cache[N]
}
if N <= 2 {
cache[1] = 1
cache[2] = 3
}
else {
cache[N] = (2 * topDown(N - 2) + topDown(N - 1)) % 10007
}
return cache[N]
}
let answer = topDown(n)
print(answer)반복문
// MARK: - 11727번(DP - 반복문)
let n = Int(readLine()!)!
var cache = Array(repeating: -1, count: 1001)
cache[1] = 1
cache[2] = 3
if n >= 3 {
for i in 3...n {
cache[i] = (2 * cache[i - 2] + cache[i - 1]) % 10007
}
}
print(cache[n])
백준 Swift 2407번
문제 유형 : DP(재귀, 반복문)
문제 자체는 사실 이항계수를 알고 있다면 풀 수 있을 것이다. 하지만 이 문제는 그것만으론 풀리지 않는다. (백준 1010번을 먼저 풀고 오는걸 추천한다.)
분명히 1010번과 동일하게 코드를 짰는데도 불구하고 틀렸다고 나온다.
처음엔 '로직 자체가 틀렸었는데, 1010번이 우연히 맞았던걸까?' 라는 생각에 다시 고민을 해봤다. 하지만 틀린 게 없었다.
질문검색을 참고하니, n과 m값이 커지면서 Int의 범위를 벗어나게 되면서 생기는 런타임오류였다.
(100 50을 입력했을 때 100891344545564193334812497256가 잘 나오는지 확인해봐라.)
(X) 생각한 방법1. Double형으로 바꾸고, 마지막에 출력 시 String(format: "%0.f", cache[n][m])을 하면 될 거라고 생각했다. 실제로 100C50이 작동해서 맞는줄 알았는데, 작동만 하는 거였지 값이 틀리게 나왔다. 숫자가 커지면서 계산에 문제가 생기는 듯 하다.
아래 더보기를 누르면 틀렸던 코드를 확인할 수 있다.
Double을 썼던, 틀린 코드.
// MARK: - 2407번(DP - 반복문)
import Foundation
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, m) = (input[0], input[1])
var cache: [[Double]] = Array(repeating: Array(repeating: -1, count: m + 1), count: n + 1)
for i in 1...n {
for j in 0...m {
if j == 0 || j == i {
cache[i][j] = 1
}
else {
cache[i][j] = cache[i - 1][j - 1] + cache[i - 1][j]
}
}
}
//print(cache[n][m])
print(String(format: "%.0f", cache[n][m]))
(O) 생각한 방법2. String으로 숫자를 계산하기로 했다. 설명을 편하게 하기 위해 문자열 a와 b로 두겠다. (a = cache[i-1][j-1], b = cache[i-1][j])
크게 4가지로 나누어 stringAdd메소드에 대해 설명하겠다.
ex) (a = "123", b = "99")
- 초기 셋팅
1. 계산을 편리하게 하기 위해, a와 b중 긴 문자열을 b로 둔다. 만약 a가 더 길다면 swap한다.
(Swift에선 String을 다루는 것보다, [String]을 다루는 게 쉽기 때문에 .map을 써서 바꾼다.)
- 첫번째 for문 흐름
2-1. 우선 a의 문자열의 길이만큼 뒤에서 for문을 돌면서 숫자(문자열)를 더한다. = sum
2-2. 예시에선 sum이 9 + 3 = 12가 되고, sum % 10 = 2를 answerString에 이어 붙인다. - answerString = "2"
2-3. carry(올려질 숫자)는 sum / 10 = 1이 되고, 다음 sum에 함께 더해진다. - answerString = "2"
2-4. sum은 9 + 2 + 1(carry) = 12이 되고, 2-2처럼 한다. - answerString = "22"
2-5. carry(올려질 숫자)는 sum / 10 = 1이 되고, 다음 sum에 함께 더해진다. - answerString = "22"
2-6. carry는 1을 갖고 두번째 for문으로 간다.
- 두번째 for문 흐름
3-1. a의 길이만큼은 이미 다 돌았으니까, b의 나머지 길이만큼만 거꾸로 더 이어 붙여주면 된다. 즉, index : len2 - len1 - 1부터 0까지다.
3-2. sum이 1 + 1(carry) = 2가 되고, sum % 10 = 2를 answerString에 이어 붙인다. - answerString = "222"
3-3. carry는 0이 된다.
- 세번째 if문
4. 이 예시에선 if문은 들어오지 않는다. 하지만 길이가 같은 a와 b였다면 이 조건문에 들어오게 된다.
예를들어 a = "9974", b = "9999" 에선 두번째 for문엔 들어가지 않고, carry는 첫번째 for문에서 1의 값을 갖고 조건문에 들어온다. (carry는 19 / 10 = 1이다.)
answerString에 carry값을 문자로 바꿔서 이어붙여주면 된다.
- 마지막 return
answerString을 뒤집어주면 두 숫자 문자열을 더할 수 있다.
이렇게 stringAdd를 만들어서 cache[i][j] = cache[i-1][j-1] + cache[i-1][j]에 적용하면 된다!
난이도 : 실버3
재귀
// MARK: - 2407번(DP - 재귀)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, m) = (input[0], input[1])
var cache: [[String]] = Array(repeating: Array(repeating: "0", count: m + 1), count: n + 1)
func stringAdd(_ a: String, _ b: String) -> String { // 큰 숫자 더하기.
var aArray = a.map{String($0)}
var bArray = b.map{String($0)}
if aArray.count > bArray.count { // b가 무조건 길게.
swap(&aArray, &bArray)
}
let len1 = aArray.count
let len2 = bArray.count
var answerString: String = ""
var carry: Int = 0 // 올림되는 숫자값
let diff = len2 - len1
for i in stride(from: len1-1, through: 0, by: -1) {
let sum: Int = Int(aArray[i])! + Int(bArray[diff + i])! + carry
answerString += String(UnicodeScalar(sum % 10 + 48)!) // 48이 "0"의 유니코드값.
carry = sum / 10
}
for i in stride(from: len2-len1-1, through: 0, by: -1) {
let sum: Int = Int(bArray[i])! + carry
answerString += String(UnicodeScalar(sum % 10 + 48)!)
carry = sum / 10
}
if carry > 0 {
answerString += String(UnicodeScalar(carry + 48)!)
}
// answerString = answerString.reversed().map{String($0)}.joined(separator: "")
answerString = String(answerString.reversed())
return answerString
}
for i in 1...n {
for j in 0...m {
if j == 0 || j == i {
cache[i][j] = "1"
}
else {
// cache[i][j] = cache[i - 1][j - 1] + cache[i - 1][j]
cache[i][j] = stringAdd(cache[i - 1][j - 1], cache[i - 1][j])
}
}
}
func topDown(_ N: Int, _ M: Int) -> String {
if cache[N][M] != "0" {
return cache[N][M]
}
if M == 0 || M == N {
cache[N][M] = "1"
}
else {
cache[N][M] = stringAdd(topDown(N - 1, M - 1), topDown(N - 1, M))
}
return cache[N][M]
}
let answer = topDown(n, m)
print(answer)반복문
// MARK: - 2407번(DP - 반복문)
import Foundation
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, m) = (input[0], input[1])
var cache: [[String]] = Array(repeating: Array(repeating: "0", count: m + 1), count: n + 1)
func stringAdd(_ a: String, _ b: String) -> String { // 큰 숫자 더하기.
var aArray = a.map{String($0)}
var bArray = b.map{String($0)}
if aArray.count > bArray.count { // b가 무조건 길게.
swap(&aArray, &bArray)
}
let len1 = aArray.count
let len2 = bArray.count
var answerString: String = ""
var carry: Int = 0 // 올림되는 숫자값
let diff = len2 - len1
for i in stride(from: len1-1, through: 0, by: -1) {
let sum: Int = Int(aArray[i])! + Int(bArray[diff + i])! + carry
answerString += String(UnicodeScalar(sum % 10 + 48)!) // 48이 "0"의 유니코드값.
carry = sum / 10
}
for i in stride(from: len2-len1-1, through: 0, by: -1) {
let sum: Int = Int(bArray[i])! + carry
answerString += String(UnicodeScalar(sum % 10 + 48)!)
carry = sum / 10
}
if carry > 0 {
answerString += String(UnicodeScalar(carry + 48)!)
}
// answerString = answerString.reversed().map{String($0)}.joined(separator: "")
answerString = String(answerString.reversed())
return answerString
}
for i in 1...n {
for j in 0...m {
if j == 0 || j == i {
cache[i][j] = "1"
}
else {
// cache[i][j] = cache[i - 1][j - 1] + cache[i - 1][j]
cache[i][j] = stringAdd(cache[i - 1][j - 1], cache[i - 1][j])
}
}
}
print(cache[n][m])
백준 Swift 11053번
문제 유형 : DP(재귀, 반복문)
- 어려웠다. 이해가 안됐다. 규칙을 찾지 못했다... 결국 다른 블로그를 참고해서 풀었다.
가장 긴 증가하는 부분 수열을 LIS(Longest Increasing Subsequence)라고 한다.
O(N^2)와 O(NlogN)으로 풀어낼 수 있다고 하는데, 우선 O(N^2)인 이중반복문으로 풀었다. 이 유형이 익숙해지면 이분탐색으로 O(NlogN)으로도 풀어볼 예정이다.
1. 모든 dp 값을 우선 1로 초기화한다.
2. 기준이 되는 aArray[i]가 aArray[j]보다 큰지 비교한다.
3. 크다면, 현재 위치(i)보다 이전 숫자들 중, dp의 최댓값 + 1이 dp[i]값이 된다.
하단 참고 링크에 있는 나무위키 글을 한번 읽어보면 이해가 빠를 것이다.
난이도 : 실버3
참고 링크 : https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4#rfn-1 | https://t.ly/sqXnQ
재귀 - 틀림
// MARK: - 11053번(DP - 재귀함수) : 틀림
let N = Int(readLine()!)!
let aArray = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp = Array(repeating: 1, count: N)
func topDown(_ index: Int) -> Int {
if dp[index] != 1 {
return dp[index]
}
for j in 0..<index {
if aArray[index] > aArray[j] {
dp[index] = max(dp[index], topDown(j) + 1)
}
}
return dp[index]
}
var maxAnswer: Int = 0
for i in 1..<N {
maxAnswer = max(maxAnswer, topDown(i))
}
print(maxAnswer)반복문(1) - 참고 코드
// MARK: - 11053번(DP - 반복문)
let N = Int(readLine()!)!
let aArray = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp = Array(repeating: 1, count: N)
for i in 1..<N {
for j in 0..<i {
if aArray[i] > aArray[j] {
dp[i] = max(dp[i], dp[j] + 1)
}
}
}
print(dp.max()!)반복문(2) - 11055번 풀고 다시 시도한 혼자 힘으로 작성한 코드. (22.04.25)
// MARK: - 11053번 다시
let N = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp = Array(repeating: 0, count: N)
dp[0] = 1
for i in 1..<N {
let standard = arr[i]
var maxValue = 0
for j in 0..<i {
if arr[j] < standard { // 기준보다 작지만,
maxValue = max(maxValue, dp[j]) // 그 중 제일 큰 dp값에
}
}
dp[i] = maxValue + 1 // 1을 더한게 dp[n]값.
}
print(dp.max()!)백준 Swift 1912번
문제 유형 : DP(재귀, 반복문)
- 문제를 보고 바로 떠오르진 않았다. 풀이방법을 매우 보고 싶었지만... 고민하고, 값을 쭉 쓰다보니 규칙이 보였다!!!
아래 사진들이 이해가 안된다면, 밑에 설명을 읽고 다시 돌아와서 보면 이해가 될 것이다.
우선 첫번째 인덱스의 값은 그 자체가 최대 합이기 때문에, cache[0] = arr[0]으로 넣는다.
cache는 그 자리에서 나올 수 있는 최대 합을 저장하는 배열이다. 그 인덱스에 있는 숫자(=arr[i])는 반드시 포함되어야 한다는 뜻이기도 하다.
그럼 생각해보자. 이해를 돕기 위해 케이스를 나눠보겠다.
case1. 지금 인덱스 전까지의 합(= cache[i-1])이 음수였는데, 지금 인덱스에 있는 값(= arr[i])이 1000으로 엄청 크다면(양수라면)?
-> 최대합 cache[i]는 arr[i]일 것이다. 음수합에 양수를 더하는 것보다 본인(arr[i])만 포함시키는게 최대 합에 가까워지지 않겠는가. 그럼 cache[i]는 (cache[i-1] + arr[i]보단) arr[i]값을 넣어야 최대 합일 것이다.
case2. 지금 인덱스 전까지의 합(= cache[i-1])이 음수였는데, 지금 인덱스에 있는 값(= arr[i])이 음수라면?
-> 최대합 cache[i]는 arr[i]일 것이다. 최대 합을 구해야 하는데, 음수를 추가로 더한다면... 더 음수가 되지 않겠는가. 그럼 그나마 이번 값(arr[i])만 넣는게 최대합에 더 가까울 것이다.
case3. 지금 인덱스 전까지의 합(= cache[i-1])이 양수였는데, 지금 인덱스에 있는 값(= arr[i])이 음수라면?
-> 최대합 cache[i]는 cache[i-1] + arr[i]일 것이다. 본인(arr[i])만 포함되거나 or 이전 양수합(cache[i-1])에 본인 음수(arr[i])을 추가한 것 중 큰 건 후자일 것이다.
case4. 지금 인덱스 전까지의 합(= cache[i-1])이 양수였는데, 지금 인덱스에 있는 값(= arr[i])이 양수라면?
-> 최대합 cache[i]는 cache[i-1] + arr[i]일 것이다. 이유는 case3과 같다. 본인(arr[i])만 포함되거나 or 이전 양수합(cache[i-1])에 본인 양수(arr[i])을 추가한 것 중 큰 건 후자일 것이다.
위의 케이스를 하나의 점화식으로 나타낼 수 있다.
=> cache[i] = max(arr[i], cache[i-1] + arr[i])
그 다음 cache값의 max를 출력해주거나, 아래 코드처럼 매번 maxValue보다 큰지 비교한뒤 maxValue값을 출력해주면 된다!
난이도 : 실버2
재귀
// MARK: - 1912번(DP - 재귀함수)
let n = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var cache = Array(repeating: 0, count: n)
func topDown(_ N: Int) -> Int {
if cache[N] != 0 {
return cache[N]
}
if N == 0 {
cache[N] = arr[0]
}
else {
cache[N] = max(arr[N], topDown(N-1) + arr[N])
}
return cache[N]
}
let _ = topDown(n-1)
print(cache.max()!)반복문
// MARK: - 1912번(DP - 반복문)
let n = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var cache = Array(repeating: 0, count: n)
cache[0] = arr[0]
var maxValue = cache[0] // cache에 있는 값 중, 최대값(최종 정답)
for i in 1..<n {
cache[i] = max(arr[i], cache[i-1] + arr[i])
if cache[i] > maxValue {
maxValue = cache[i]
}
}
print(maxValue)
백준 Swift 11055번
문제 유형 : DP(재귀, 반복문)
- 비슷한 문제인 11053번문제는 못풀었었는데, 이번 문제는 도움 하나도 없이 풀었다!
지난번 11053번을 풀면서 참고했던 풀이보다, 이번에 풀면서 작성하게 된 코드가 내겐 더 이해가 쉬운 것 같다.
쭉 적으면서 생각해보니 규칙이 보였다.
=> 자신(arr[n])보단 작고, 그 중 제일 큰 dp값에 본인값(arr[n])을 더한게 dp[n]이다.
하단에 코드&주석을 보고 다시 이 문장을 보면 이해가 될 것이다.
난이도 : 실버2
반복문
// MARK: - 11055번(DP - 바텀업)
let N = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp = Array(repeating: 0, count: N)
dp[0] = arr[0]
for i in 1..<N {
let standard = arr[i] // 기준(자신)
var maxValue = 0
for j in 0..<i {
if arr[j] < standard { // 기준보단 작지만,
maxValue = max(maxValue, dp[j]) // 그 중 제일 큰 dp값에
}
}
dp[i] = maxValue + standard // 자기자신을 더한게 dp[n]값.
}
print(dp.max()!)
백준 Swift 1890번
문제 유형 : DP(재귀, 반복문), DFS
- 문제를 보자마자 DFS나 BFS가 떠올랐다. 방문체크도 필요 없어보였다. 그렇게 DFS와 BFS로 풀어봤다. 결과는 둘 다 시간초과다. 관련 코드는 아래에 더보기를 누르면 확인할 수 있다.
사람들이 많이 푼 bottomUp(dp테이블) 방법이 제일 무난하고 쉬운 것 같다.
dfs와 dp를 합쳐서 푼 topDown방식은, 고려해야 할 게 있어서 bottomUp방식보다 더 어려운 것 같다.
난이도 : 실버2
dp없이 DFS or BFS로만 풀면 테스트케이스는 나오지만, 시간초과가 난다.
BFS - 시간초과
// MARK: - 1890번(BFS - 시간초과)
let N = Int(readLine()!)!
var map: [[Int]] = Array(repeating: [], count: N)
for i in 0..<N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
map[i] = input
}
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y < N) && (0 <= x && x < N)
}
var answerCount: Int = 0
func bfs(_ startY: Int, _ startX: Int) {
var q: [(Int, Int)] = [(startY, startX)]
while !q.isEmpty {
let (y, x) = q.removeFirst()
if (y == N - 1) && (x == N - 1) { // 목적지에 도달하면,
answerCount += 1 // 경로 개수 1 증가.
continue
}
// if map[y][x] == 0 {
// continue
// }
let ny = y + map[y][x] // 밑으로 가게 될 때의 다음 y좌표.
let nx = x + map[y][x] // 우측으로 가게 될 때의 다음 x좌표.
if isValidCoord(ny, x) { // 1. 밑으로 갈 때,
q.append((ny, x))
}
if isValidCoord(y, nx) { // 2. 우측으로 갈 때,
q.append((y, nx))
}
}
}
bfs(0, 0)
print(answerCount)DFS - 시간초과
// MARK: - 1890번(DFS - 시간초과)
let N = Int(readLine()!)!
var map: [[Int]] = Array(repeating: [], count: N)
for i in 0..<N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
map[i] = input
}
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y < N) && (0 <= x && x < N)
}
var answerCount: Int = 0
func dfs(_ y: Int, _ x: Int) {
if y == N - 1 && x == N - 1 {
answerCount += 1
}
else {
let ny = y + map[y][x]
let nx = x + map[y][x]
if isValidCoord(ny, x) { // 1. 밑으로 갈 때,
dfs(ny, x)
}
if isValidCoord(y, nx) { // 2. 우측으로 갈 때,
dfs(y, nx)
}
}
}
dfs(0, 0)
print(answerCount)
재귀
map[y][x]값이 0일때 맴돌게 되기 때문에, 맴도는걸 방지하기 위해 처음에 cache를 -1로 초기화 후 방문 시 0으로 초기화해준다.
참고 링크 : https://sihyungyou.github.io/baekjoon-1890/
// MARK: - 1890번(DFS, DP - topDown)
let N = Int(readLine()!)!
var map: [[Int]] = Array(repeating: [], count: N)
var cache = Array(repeating: Array(repeating: -1, count: N), count: N)
for i in 0..<N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
map[i] = input
}
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y < N) && (0 <= x && x < N)
}
func dfs(_ y: Int, _ x: Int) -> Int { // topDown
if y == N - 1 && x == N - 1 {
return 1
}
else if cache[y][x] == -1 {
cache[y][x] = 0
let ny = y + map[y][x]
let nx = x + map[y][x]
if isValidCoord(ny, x) { // 1. 밑으로 갈 때,
cache[y][x] += dfs(ny, x)
}
if isValidCoord(y, nx) { // 2. 우측으로 갈 때,
cache[y][x] += dfs(y, nx)
}
}
return cache[y][x]
}
let answer = dfs(0, 0)
//print(cache)
print(answer)반복문
참고 링크 : https://dailymapins.tistory.com/m/91
// MARK: - 1890번(DP - 반복문)
let N = Int(readLine()!)!
var map: [[Int]] = Array(repeating: [], count: N)
var cache = Array(repeating: Array(repeating: 0, count: N), count: N)
for i in 0..<N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
map[i] = input
}
func isValidCoord(_ y: Int, _ x: Int) -> Bool {
return (0 <= y && y < N) && (0 <= x && x < N)
}
cache[0][0] = 1
for y in 0..<N {
for x in 0..<N {
if cache[y][x] != 0 && map[y][x] != 0 {
let ny = y + map[y][x]
let nx = x + map[y][x]
if isValidCoord(ny, x) { // 1. 밑으로 갈 때,
cache[ny][x] += cache[y][x]
}
if isValidCoord(y, nx) { // 2. 우측으로 갈 때,
cache[y][nx] += cache[y][x]
}
}
}
}
print(cache[N-1][N-1])
백준 Swift 9465번
문제 유형 : DP(재귀, 반복문)
- 총 3번의 시도끝에 풀었다. 결국 다른 블로그를 참고했다.
첫번째 시도
: 처음엔 dp배열을 1차원배열로 하면 된다고 생각했다. 이유는 아래 사진처럼 나열해봤을 때, 규칙을 발견한 거 같았기 때문이다. 근데 dp[4]에서 안되는 거 보고 틀린걸 깨달았다.
두번째, 세번째 시도
: 블로그를 참고해서 dp를 2차원배열로 선언하면 된다는걸 깨달았다. dp를 2차원배열로 하고,
바로 대각선(0행 기준 dp[1][i-1]) or 한칸 간 뒤 대각선(0행 기준 dp[1][i-2]) 중에 큰 걸 선택하면 된다. + arr[0][i]
똑같은 로직인데도 불구하고 두번째 시도는 왜 틀렸냐면, 0열과 1열일 때 arr의 값을 넣은게 아니라 그 행에서 나올 수 있는 최댓값으로 넣었더니 틀렸다. 잘 생각해보면, 이렇게 하면 예시 testcase는 맞는데 아래 반례는 틀린다.
처음엔 틀려서 당황했는데, 아래 반례를 보고 생각해보니 2행에서부터 문제가 생긴다.
점화식
0행 : dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + arr[0][i]
1행 : dp[1][i] = max(dp[0][i-1], dp[0][i-2]) + arr[1][i]
난이도 : 실버1
아래 더보기 - 반례
반례
1
4
100 1 1 100
1 1 100 1
반복문
// MARK: - 9465번(DP - 반복문)
let T = Int(readLine()!)!
for _ in 0..<T {
let n = Int(readLine()!)!
var arr: [[Int]] = Array(repeating: [], count: 2)
arr[0] = readLine()!.split(separator: " ").map{Int(String($0))!}
arr[1] = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp = Array(repeating: Array(repeating: -1, count: n), count: 2)
dp[0][0] = arr[0][0] // a
dp[1][0] = arr[1][0] // b
if n >= 2 {
dp[0][1] = arr[1][0] + arr[0][1] // (b+c)
dp[1][1] = arr[0][0] + arr[1][1] // (a+d)
for i in 2..<n {
dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + arr[0][i] // 위쪽
dp[1][i] = max(dp[0][i-1], dp[0][i-2]) + arr[1][i] // 아래쪽
}
}
let answer = max(dp[0][n-1], dp[1][n-1])
print(answer)
}처음짠 잘못된 코드
// MARK: - 9465번(DP - 처음짠 잘못된 코드)
let T = Int(readLine()!)!
for _ in 0..<T {
let n = Int(readLine()!)!
var arr: [[Int]] = Array(repeating: [], count: 2)
arr[0] = readLine()!.split(separator: " ").map{Int(String($0))!}
arr[1] = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp = Array(repeating: -1, count: n + 1)
dp[1] = max(arr[0][0], arr[1][0]) // max(a, b)
dp[2] = max(arr[0][0] + arr[1][1], arr[1][0] + arr[0][1]) // max(a+d, b+c)
for i in 3...n {
dp[i] = max(dp[i-1], dp[i-2]) + max(arr[0][i-1], arr[1][i-1])
}
print(dp)
}백준 Swift 15486번
문제 유형 : DP(재귀, 반복문)
- 고민해봤는데 모르겠어서 다른 블로그를 참고했다.
dp배열의 값들은 그 날에 받을 수 있는 최대금액을 의미한다.
각 @일에서 next를 생각해야 하는게 핵심인 것 같다.
점화식에서 dp[next]를 할 때 자기자신(dp[next])과 비교하는 이유는, 이미 이전 @일차에서 next일차에 접근했을 때의 값이 더 클 수가 있기 때문이다.
주의사항 2가지
1. 점화식에서, dp[i]값이 아니라 maxValue값으로 해야 한다. 그렇지 않으면 지금까지 쌓인 금액을 제대로 끌고 올라갈 수 없다.(바텀업이니까.. 이해가 되려나?)
테스트케이스1~3에선 최소 한번씩은 접근을 했기 때문에 dp[i]로 해도 문제가 안생겼는데, 테스트케이스4의 8일차에서는 이미 많이 진행됐음에도 불구하고 첫접근이여서 문제가 생기는 것이었다.
테스트케이스4에서, 8일차일 때 dp[next]값은 90이 돼야 하는데, dp[i]로 하게 되면 30이 된다. (=8일차 전까지 이미 쌓인 (최대)금액 50 + 10이 계산이 안된다는 뜻이다.)
이해가 안된다면 테스트케이스4를 함께 돌리면서 글을 다시 읽어봐라. 빠르게 이해 될 것이다.
2. 마지막 날에 Tn이 1이라면 근무가 가능하다. 이게 무슨 뜻일까? 힌트는 dp배열의 길이와 관련이 있다.
=> 즉, N일차때의 계산을 위해 dp배열을 1칸 더 늘려줘야 한다는 뜻이다.(드래그를 하면 볼 수 있다.)
점화식
i일차 일 때,
next = i + Ti
dp[next] = max(dp[next],dp[i]+ Pi) -> dp[next] = max(dp[next], maxValue + Pi)
난이도 : 실버1
참고 링크 : https://loosie.tistory.com/219
반복문
// MARK: - 15486번(DP - 반복문)
let N = Int(readLine()!)!
var T: [Int] = [0] + Array(repeating: 0, count: N) // 0일 제외
var P: [Int] = [0] + Array(repeating: 0, count: N) // 0일 제외
for i in 1...N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (time, pay) = (input[0], input[1])
T[i] = time
P[i] = pay
}
var dp: [Int] = [0] + Array(repeating: 0, count: N) + [0] // 0일 제외, N개 + 1개(마지막날의 T값이 1일 땐 근무 가능. -> 그 값을 저장하기 위해 배열 1 증가시킴.)
var maxValue: Int = -1
for i in 1...N {
let next = i + T[i]
maxValue = max(maxValue, dp[i]) // 이전까지의 최대값을 계속 갖고 있어야 함.
if next <= N + 1 {
// dp[next] = max(dp[next], dp[i] + P[i])
dp[next] = max(dp[next], maxValue + P[i]) // dp[i]가 아니라 maxValue여야 됨. 예제4에서 틀려서 확인.
}
}
print(dp.max()!)
백준 Swift 2156번
문제 유형 : DP(재귀, 반복문)
- 예제 TC는 맞아서 처음엔 맞게 푼 것 같았다. 사실 문제를 보고 어떤 규칙이 없을까 라고 생각하고 무작정 돌입해서 푼 것 같다. min을 생각하고 있었으니...
결국 틀렸고 다른 블로그를 참고했다.
현재 잔을 기준으로, 총 3가지의 case로 나뉜다.
case1 : 현재 잔(인덱스 i) + 직전 잔 + (3잔연속은 불가능하기 때문에) i-3위치의 최대값
case2 : 현재 잔(인덱스 i) + (직전 잔은 패스) + i-2위치의 최대값
case3 : (현재 잔 패스) + i-1위치의 최대값
따라서 점화식은 다음과 같다.
(i >= 4)
case1 : arr[i] + arr[i-1] + dp[i-3]
case2 : arr[i] + dp[i-2]
case3 : dp[i-1]
-> dp[i] = max(case1, case2, case3)
난이도 : 실버1
참고 링크 : https://myjamong.tistory.com/313
재귀
// MARK: - 2156번(DP - 재귀함수)
let n = Int(readLine()!)!
var arr = [0] + Array(repeating: 0, count: 10000) // 0번째는 무시.
var dp = [-1] + Array(repeating: -1, count: 10000) // 0번째는 무시.
for i in 1...n {
arr[i] = Int(readLine()!)!
}
func topDown(_ N: Int) -> Int {
if dp[N] != -1 {
return dp[N]
}
if N <= 3 {
dp[1] = arr[1]
dp[2] = arr[1] + arr[2]
dp[3] = max(arr[1] + arr[2], arr[1] + arr[3], arr[2] + arr[3]) // 인덱스 1 + 2, 1 + 3, 2 + 3
}
else {
let case1 = arr[N] + arr[N - 1] + topDown(N - 3) // 현재잔 + 직전잔 + N-3위치의 최대값
let case2 = arr[N] + topDown(N - 2) // 현재잔 + N-2위치의 최대값
let case3 = topDown(N - 1) // 현재잔X -> N-1위치의 최대값
dp[N] = max(case1, case2, case3)
}
return dp[N]
}
print(topDown(n))반복문
// MARK: - 2156번(DP - 반복문)
let n = Int(readLine()!)!
var arr = [0] + Array(repeating: 0, count: 10000) // 0번째는 무시.
var dp = [0] + Array(repeating: 0, count: 10000) // 0번째는 무시.
for i in 1...n {
arr[i] = Int(readLine()!)!
}
dp[1] = arr[1]
dp[2] = arr[1] + arr[2]
dp[3] = max(arr[1] + arr[2], arr[1] + arr[3], arr[2] + arr[3]) // 인덱스 1 + 2, 1 + 3, 2 + 3
if n >= 4 {
for i in 4...n {
let case1 = arr[i] + arr[i - 1] + dp[i - 3] // 현재잔 + 직전잔 + i-3위치의 최대값
let case2 = arr[i] + dp[i - 2] // 현재잔 + i-2위치의 최대값
let case3 = dp[i - 1] // 현재잔X -> i-1위치의 최대값
dp[i] = max(case1, case2, case3)
}
}
print(dp.max()!)
틀린 코드
// MARK: - 2156번(DP - 반복문 : 틀린코드)
let n = Int(readLine()!)!
var arr = [0] + Array(repeating: 0, count: n) // 0번째는 무시.
var dp = [0] + Array(repeating: 0, count: n) // 0번째는 무시.
for i in 1...n {
arr[i] = Int(readLine()!)!
}
dp[1] = arr[1]
var minValue: Int = arr[1]
dp[2] = max(minValue + arr[2], arr[2]) // 무조건 arr[1] + arr[2]가 클 수 밖에 없긴 함.
minValue = min(minValue + arr[2], arr[2]) // 무조건 arr[2]가 작을 수 밖에 없긴 함.
if n >= 3 {
for i in 3...n {
dp[i] = max(minValue + arr[i], dp[i-2] + arr[i])
minValue = min(minValue + arr[i], dp[i-2] + arr[i])
}
}
print(dp)
print(dp.max()!)백준 Swift 10844번
문제 유형 : DP(재귀, 반복문)
- 처음 고민한 방식은 틀렸다. 모르겠어서 다른 블로그를 참고했다.
dp를 2차원 배열로 생각하니까 접근이 가능했다.
이전 길이(N-1)의 수에서, 끝자리(일의 자리)가 0이라면 -> 이번 길이(N)의 끝자리는 1.
이전 길이(N-1)의 수에서, 끝자리(일의 자리)가 9라면 -> 이번 길이(N)의 끝자리는 8.
이전 길이(N-1)의 수에서, 끝자리(일의 자리)가 1~8이라면 -> 이번 길이(N)의 끝자리는 +-1.
방금 위 3줄을 다시 생각해보면,
이번 길이(N)의 끝자리가 0일때의 값 dp[N][0]은, dp[N-1][1]일 것이다.
이번 길이(N)의 끝자리가 9일때의 값 dp[N][9]은, dp[N-1][8]일 것이다.
이번 길이(N)의 끝자리가 1~8일때의 값 dp[N][1] ~ dp[N][8]은, dp[N-1][+-1]일 것이다.
점화식은 아래의 이미지를 보면 이해가 쉬울 것이다.
주의! mod를 answer 출력할 때도 빼트리면 안된다! (https://www.acmicpc.net/board/view/7755)
난이도 : 실버1
참고 링크 : https://t.ly/VYMC | https://st-lab.tistory.com/134 | https://www.acmicpc.net/board/view/7755
재귀
// MARK: - 10844번(DP - 재귀함수)
let N = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count: 10), count: N + 1)
let mod = 1000000000 // mod로 나눈 나머지.
var sum: Int = 0
for j in 0...9 {
sum += topDown(N, j) % mod
}
print(sum % mod) // mod 빼먹으면 안됨.
func topDown(_ n: Int, _ lastNum: Int) -> Int {
if dp[n][lastNum] != 0 {
return dp[n][lastNum]
}
if n == 1 { // 1일땐 미리 세팅.
dp[n][lastNum] = 1
dp[n][0] = 0
}
else { // n >= 2일 때,
if lastNum == 0 {
dp[n][lastNum] = topDown(n - 1, 1)
}
else if lastNum >= 1 && lastNum <= 8 {
dp[n][lastNum] = (topDown(n - 1, lastNum - 1) + topDown(n - 1, lastNum + 1))
}
else if lastNum == 9 {
dp[n][lastNum] = topDown(n - 1, 8)
}
}
return dp[n][lastNum] % mod
}반복문
// MARK: - 10844번(DP - 반복문)
let N = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count: 10), count: N + 1)
for j in 1...9 { // N은 1이고, 1부터 9일 때
dp[1][j] = 1
}
let mod = 1000000000 // mod로 나눈 나머지.
if N >= 2 {
for i in 2...N {
for j in 0...9 {
if j == 0 {
dp[i][j] = (dp[i - 1][1]) % mod // = dp[i-1][j+1] % mod
}
else if j >= 1 && j <= 8 {
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod
}
else if j == 9 {
dp[i][j] = (dp[i - 1][8]) % mod // = dp[i-1][j-1] % mod
}
}
}
}
let sum = dp[N].reduce(0, +) % mod // 길이가 N인 계단 수의 개수.
print(sum)틀린 코드
// MARK: - 10844번(DP - 반복문: 틀림)
let N = Int(readLine()!)!
var dp: [Int] = [0] + Array(repeating: 0, count: N)
dp[1] = 9
if N >= 2 {
for i in 2...N {
dp[i] = (2 * dp[i - 1] - 1) % 1000000000
}
}
print(dp[N])
최근댓글