Hyun's_Devlog

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])

정답 코드

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

처음엔 그래프 탐색으로 접근했지만, DP로 해결한 문제다.

풀이

최대 점수를 담는 3칸 크기 배열과 최소 점수를 담는 3칸 크기 배열을 생성한 뒤 매 입력마다 최대, 최소 점수를 누적해 나가면 된다.

단, 갱신되는 주체가 무엇인지를 잘 생각해야한다. 예제를 기준으로 표를 그려봤다.

첫 입력은 당연히 그대로 입력받고 두번째 입력부터 비교를 시작한다. 현재 입력값 기준으로 이전 입력값들의 비교를 통해서 값을 경신해야 한다. 본인은 아무 생각 없이 이전 배열을 기준으로 새로 입력받은 값을 경신해서 오답을 받았다.

마지막 결과인 [12 18 19] 배열 중 가장 큰값이 최댓값이 된다. 최솟값은 반대로 최솟값들로 연상하여 갱신하면 된다.

정답 코드

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

dp문제다. 완전 탐색으로 시도했지만 역시나 시간 초과. 점화식을 생각해내는 데에 시간이 걸렸던 문제다.

풀이

최소한의 정사각형을 만들 수 있는 칸부터 시작해야 한다. 2차원 배열 map에 대해서 x와 y의 값이 모두 1 이상이고 map[x][y]의 값이 0보다 커야 한다. 해당 좌표의 상, 좌, 좌대각선 칸 중 최솟값 + 1로 갱신해나가면 된다.

map[x][y] = min(min(map[x-1][y], map[x][y-1]), map[x-1][y-1]) + 1

정답 코드

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

답이 생각나지 않아 점화식을 찾아보고 코드를 적어봤는데, 풀이를 이해하고서도 예외처리를 제대로 하지 못해서 오답 판정을 받았다. 결국 코드까지 찾아보고 난 후에야 풀 수 있었던 문제. 역시나 DP문제는 다양한 시점으로 생각하는 연습이 필요한 것 같다.

풀이

암호화된 문자의 길이가 n일 경우, dp:[Int] 배열은 총 n개의 배열로 dp[i]는 0번째 숫자부터 i번째 숫자까지로 만들수 있는 암호의 갯수가 담긴 배열이다. 입력된 암호문구를 순회하면서 현재 숫자가 0보다 크다면 dp[i-1]번째 경우의 수를 이어가면 되고, 추가로 직전 숫자가 0보다 크다면 현재 숫자와 합쳐 두 자리수의 대체 가능한 알파벳을 만들수 있다면 dp[i-2]번째 경우의 수를 추가로 이어가면된다. 즉 점화식은 아래와 같다.

현재 암호가 0보다 크다면,
dp[i] += dp[i-1]
추가로 직전 암호가 0보다 커서 현재 암호와 이어 붙였을 시 10 이상 26 이하라면,
dp[i] += dp[i-2]

점화식을 알았을 때는 간단하게 풀면 되겠다 싶었는데, 문제는 중간에 나오는 0에 대한 처리 부분이었다. 처음에는 중간에 flag 변수를 만들어 분기 처리를 하였는데, 생각보다 처리해야 할 경우가 많아서 오답처리를 받았다. 다른 유형의 문제들은 많은 문제를 풀면서 패턴에 적응해가는 과정을 통해 성장해가는 게 느껴지는 반면, DP문제는 다양한 시각에서 문제를 바라봐야 한다는 점이 여러모로 어렵게 느껴진다. 풀이는 해당 블로그에서 찾았다. 이해하기 쉽게 풀이에 대한 이미지도 있다.

정답 코드

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

대표적인 동적 계획법 문제이다. 동적 계획법은 항상 마주할 때마다 느끼듯이 점화식을 고민하는 데에 너무 오랜 시간이 걸린다. 더 많은 문제들을 풀어봐야 하나 보다.

풀이

정답을 표현할 배열 dp는 n+1개의 요소를 가지는 배열이며, dp[n]은 "1,2,3을 사용하여 n을 만들 수 있는 식의 개수"라고 정의한다.

점화식을 사용하기 위해서 배열에 최소 3개의 요소가 담겨있어야 한다. 1부터 3까지의 경우의 수를 적어보면 다음과 같다.

이후 1,2,3을 이용해 4를 만드는 식을 만든다고 가정할 경우, 다음과 같은 생각을 해볼 수 있다.

1. 1을 만들 수 있는 모든 식에 "+3"을 추가한다면 4를 만들 수 있다.
2. 2를 만들 수 있는 모든 식에 "+2"를 추가한다면 4를 만들 수 있다.
3. 3을 만들 수 있는 모든 식에 "+1"을 추가한다면 4를 만들 수 있다.

따라서 다음과 같은 점화식을 세울수있게된다.

dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

다만 문제를 보면 알 수 있듯이 n의 크기가 1,000,000이므로 정답을 출력할 때 1,000,000,009로 나눈 나머지를 출력하라고 적혀있다.

모듈러 산술 연산법칙은 분배 법칙이 성립하므로 코드를 적을 때는 다음과 같이 적는다.

dp[n] = ((dp[n-1]%1,000,000,009) + (dp[n-2]%1,000,000,009) + (dp[n-3]%1,000,000,009))%1,000,000,009

정답 코드

import Foundation

var dp = Array(repeating: 0, count: 1000001)
dp[1] = 1
dp[2] = 2
dp[3] = 4
let mod = 1000000009

for i in 4...1000000{
    dp[i] = ((dp[i-1]%mod) + (dp[i-2]%mod) + (dp[i-3]%mod))%mod
}

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

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

풀이

동적 계획법 문제이다. 처음에는 깊이 우선 탐색으로 시도했으나 시간 초과가 발생. 동적 계획법 문제로 분류되어있는 걸 확인하고 난 후 고민했으나, 결국 다른 사람의 풀이과정을 이해하고 코드를 다시 작성하였다.

시간 초과 코드

import Foundation

let n = Int(readLine()!)!

var map = Array(repeating: [Int](), count: n)
for i in 0..<n{
    map[i] = readLine()!.split(separator: " ").map{Int($0)!}
}
var ans = 0

func dfs(x:Int, y:Int){
    if map[x][y]==0{
        if x==n-1 && y==n-1{
            ans += 1
        }
        return
    }
    let length = map[x][y]
    if x+length<n{
        dfs(x: x+length, y: y)
    }
    if y+length<n{
        dfs(x: x, y: y+length)
    }
}
dfs(x: 0, y: 0)
print(ans)

해결 코드

import Foundation

let n = Int(readLine()!)!

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

dp[0][0]=1
for x in 0..<n{
    for y in 0..<n{
        if map[x][y]==0 || dp[x][y]==0{continue}
        let nx = x + map[x][y]
        let ny = y + map[x][y]
        if nx<n{ dp[nx][y] += dp[x][y]}
        if ny<n{ dp[x][ny] += dp[x][y]}
    }
}
print(dp[n-1][n-1])