여러 개의 하위 문제를 풀고 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘
예 ) 피보나치
-> 백트래킹 하기엔 n이 너무 클 경우
DP 푸는 과정
1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 찾기
구현은 쉽지만 점화식을 끌어내는 과정이 쉽지 않음 -> 많은 문제 풀이 필요
(세 방향(연산 종류)으로 전개되는 bfs로도 풀 수 있음)
1.테이블 정의하기
d[i] = i 를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값
2. 점화식 찾기 (최소 횟수를 만들기 위한 규칙 찾기)
- 3으로 나누기 : d[k] = d[k/3] + 1(3으로 나눈 횟수 추가)
- 2로 나누기 : d[k] = d[k/2] + 1(2로 나눈 횟수 추가)
- 1 빼기 : d[k] = d[k-1] + 1(1뺀 연산 횟수 추가)
-> d[k] = min(d[k/3] + 1, d[k/2] + 1, d[k-1] + 1)
할 수 있는 세가지 연산 중 최솟값이 d[k]의 값이다
3. 초기값 정의하기
d[1] = 0
코드
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.min
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val d = IntArray(n+1) { 0 }
d[1] = 0
for (i in 2..n) {
d[i] = d[i-1] + 1 // 1을 뺀 경우
if (i % 3 == 0) d[i] = min(d[i],d[i/3] + 1 )// 3으로 나눈 경우
if (i % 2 == 0) d[i] = min(d[i], d[i/2] + 1) // 2로 나눈 경우
}
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write("${d[n]}")
bw.close()
}
(백트래킹으로도 가능하지만 n이 커질 경우에는 불가능)
1. 테이블 정의하기
d[i] = i를 1,2,3의 합으로 나타내는 방법의 수
2. 점화식 찾기
정수가 4일 때 1,2,3의 합으로 나타내는 방법은 총 7가지가 있다
1+1+1+1, 1+2+1, 2+1+1, 3+1 -> 맨 마지막에 더하는 값이 1인 경우 -> 1,2,3 으로 3을 만드는 방법 + 1
1+1+2, 2+2 -> 맨 마지막에 더하는 값이 2인 경우 -> 1,2,3으로 2를 만드는 방법 + 2
1+3 -> 맨 마지막에 더하는 값이 3인 경우 -> 1, 2, 3으로 1을 만드는 방법 + 3
d[4] = d[1] + d[2] + d[3]
-> d[k] = d[k-3] + d[k-2] + d[k-1]
3. 초기값 정하기
d[1] = 1
d[2] = 2
- 1+1
- 2
d[3] = 4
- 1+1+1
- 1+2
- 2+1
- 3
코드
import java.io.*
import java.lang.StringBuilder
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
var t = readLine().toInt()
val sb = StringBuilder()
val d = IntArray(11) { -1 }
d[1] = 1
d[2] = 2
d[3] = 4
while (t-- != 0) {
val n = readLine().toInt()
for (i in 4..n) {
// 저장된 d[i] 값 사용하기
if (d[i] == -1) d[i] = d[i-1] + d[i-2] + d[i-3]
}
sb.append("${d[n]}\n")
}
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write(sb.toString())
bw.close()
}
BOJ 2579. 계단 오르기
계단 오르는 조건
- 한 번에 한 계단 혹은 두 계단씩 오를 수 있다
- 연속된 세 개의 계단을 모두 밟아서는 안된다 (1-> 2 -> 3 불가능)
- 마지막 도착 계단은 반드시 밟아야 한다
계단이 여섯 개일 때, 마지막 도착 계단을 밟기 위해서는
- 네 번째 계단을 밟는다 (규칙 2에 의하여 다섯 번째 계단은 밟을 수 없다)
- 다섯 번째 계단을 밟는다 (규칙 2에 의하여 네 번째 계단을 밟을 수 없다)
1. 테이블 정의하기
d[i] = i번째 계단까지 올라섰을 때 점수 합의 최댓값
2. 점화식 찾기
마지막 칸을 밟는 방법
1. 전칸을 밟는 경우 (전전칸을 밟을 수 없기 때문에 전전전칸을 밟아야 한다)
d[k] = s[k-1] + d[k-3] + s[k]
2. 전전칸을 밟는 경우
d[k] = d[k-2] + s[k]
d[k] = max(s[k-1] + d[k-3], d[k-2]) + s[k]
3. 초기값 정하기
d[1] = s[1]
d[2] = s[1] + s[2] // 2를 밟는 경우는 두개가 있지만 당연히 1->2 둘다 밟는게 최댓값
d[3] = max(s[1], s[2]) + s[3] // 1-> 3 or 2 -> 3
코드
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.max
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val s = IntArray(n+1)
// 1번 계단부터 시작
for (i in 1..n) {
s[i] = readLine().toInt()
}
val d = IntArray(n+1) { 0 }
d[1] = s[1] // 첫번째 계단을 밟는 경우 점수 합
if (n > 1) d[2] = s[1] + s[2] // 두번째 계단을 밟는 경우 점수 합의 최댓값
if (n > 3) d[3] = max(s[1], s[2]) + s[3] // 세번째 계단을 밟는 경우 점수 합의 최댓값
for (i in 4..n) {
d[i] = max(s[i-1] + d[i-3], d[i-2]) + s[i]
}
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write("${d[n]}")
bw.close()
}
- n번 집의 색은 n-1번 집의 색과 같지 않아야 한다
- i번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다 (i in 2..n-1)
1. 테이블 정의하기
d[i][0] = i번째 집까지 칠할 때 비용의 최솟값, 단 i번째 집은 빨강
d[i][1] = i번째 집까지 칠할 때 비용의 최솟값, 단 i번째 집은 초록
d[i][2] = i번째 집까지 칠할 때 비용의 최솟값, 단 i번째 집은 파랑
2. 점화식 찾기
d[k][0] = min(d[k-1][1], d[k-1][2]) + r[k] // k-1번째 집은 초록 혹은 파랑으로 칠하기 가능
d[k][1] = min(d[k-1][0], d[k-1][2]) + g[k] // k-1번째 집은 빨강 혹은 파랑으로 칠하기 가능
d[k][1] = min(d[k-1][0], d[k-1][1]) + b[k] // k-1번째 집은 빨강 혹은 초록으로 칠하기 가능
3.초기값 정하기
d[1][0] = r[1]
d[1][1] = g[1]
d[1][2] = b[1]
코드
import java.util.*
import java.io.*
import kotlin.math.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val r = IntArray(n+1)
val g = IntArray(n+1)
val b = IntArray(n+1)
var st: StringTokenizer
for (i in 1..n) {
st = StringTokenizer(readLine())
r[i] = st.nextToken().toInt()
g[i] = st.nextToken().toInt()
b[i] = st.nextToken().toInt()
}
val d = Array(n+1) { IntArray(3) }
d[1][0] = r[1]
d[1][1] = g[1]
d[1][2] = b[1]
for (i in 2..n) {
d[i][0] = min(d[i-1][1], d[i-1][2]) + r[i] // 빨간집일 경우 이전 집은 초록, 파랑 가능
d[i][1] = min(d[i-1][0], d[i-1][2]) + g[i]
d[i][2] = min(d[i-1][0], d[i-1][1]) + b[i]
}
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write("${min(min(d[n][0], d[n][1]), d[n][2])}")
bw.close()
}
1. 테이블 정의하기
d[i] = 2 * i 크기의 직사각형을 채우는 방법의 수
2. 점화식 찾기
d[1] = 1
d[2] = 2
d[3] = 3
d[4] = 5
결국에는 두가지 모양의 반복이다
| 2*1 | 2 * (n-1) |
| 1*2 | 2 *(n-2) |
| 1*2 |
d[i] = d[i-1] + d[i-2]
3. 초기값 설정
d[1] = 1
d[2] = 2
코드
import java.io.*
fun main(args: Array<String>) {
val n = readLine()!!.toInt()
val d = IntArray(1005)
d[1] = 1
d[2] = 2
for (i in 3..n) {
d[i] = (d[i-1] + d[i-2]) % 10007
}
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write("${d[n]}")
bw.close()
}
최대 N번의 수를 더해야 하며 이걸 최대 M번 반복해야 하기 때문에 O(NM)이다
그런데 N과 M의 범위 최대가 100,000이라 일반 반복문으로는 시간초과가 날 것이다.
1. 테이블 정의하기
d[i] = i번째까지의 합인데
2. 점화식 구하기
prefix sum : 구간 합 알고리즘을 적용하면
// a는 값이 있는 배열
prefixSum[i] = prefixSum[i-1] + a[i]
d[i] = d[i-1] + a[i] 이렇게 표현할 수 있다
3. 초기값 설정하기
d[1] = a[1]
i에서 j까지 구간 합을 구하는 법
a(1, 2, 3, 4, ... i... j) 일때, i에서 j까지의 구간합은 다음과 같다
(a[1] + a[2] + a[3] + ... + a[j]) - (a[1] + a[2] + a[3] + ...+ a[i-1])
따라서 d[j] - d[i-1]로 표현할 수 있다
코드
import java.util.*
import java.io.*
import java.lang.StringBuilder
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
var st = StringTokenizer(readLine())
val n = st.nextToken().toInt()
var m = st.nextToken().toInt()
st = StringTokenizer(readLine())
val arr = IntArray(n+1)
for (i in 1..n) {
arr[i] = st.nextToken().toInt()
}
val sb = StringBuilder()
val d = IntArray(n+1)
d[1] = arr[1]
// d 테이블 값 채우기
for (i in 1..n) {
d[i] = d[i-1] + arr[i]
}
while (m-- != 0) {
st = StringTokenizer(readLine())
val i = st.nextToken().toInt()
val j = st.nextToken().toInt()
// 구간 합 구하기
sb.append("${d[j] - d[i-1]}\n")
}
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write(sb.toString())
bw.close()
}
BOJ 12852. 1로 만들기 2 : DP에서 경로 추적하기
연산을 하는 횟수의 최솟값을 출력하고 거기에 추가로 n을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분하여 출력한다
최솟값을 구하는 히스토리를 출력하는 것이다
1. 테이블 정의하기
d[i] = i를 1로 만들기 위해 필요한 연산을 하는 횟수의 최솟값
2. 점화식 구하기
d[i]에 적용할 수 있는 연산
- d[i] = d[i-1] + 1
- d[i] = d[i/2] + 1
- d[i] = d[i/3] + 1
d[i] = min(연산1, 연산2, 연산3) 이다
3. 초기값 설정하기
d[1] =0
히스토리를 출력하기 위해선 값 테이블 이외에도 추가적인 테이블이 필요하다
값 테이블(d)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 1 | 1 | 2 | 3 | 2 | 3 |
히스토리 테이블(pre)
| num | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 최적경로 | 0 | 1 | 1 | 2 | 4 | 3 | 6 |
코드
import java.io.BufferedWriter
import java.io.OutputStreamWriter
fun main(args: Array<String>) {
val n = readLine()!!.toInt()
val d = IntArray(n + 1)
val pre = IntArray(n + 1)
d[1] = 0
for (i in 2..n) {
d[i] = d[i - 1] + 1
pre[i] = i - 1
if (i % 3 == 0 && d[i] > d[i / 3] + 1) {
d[i] = d[i / 3] + 1
pre[i] = i / 3
}
if (i % 2 == 0 && d[i] > d[i / 2] + 1) {
d[i] = d[i / 2] + 1
pre[i] = i / 2
}
}
val bw = BufferedWriter(OutputStreamWriter(System.out))
// 최소 연산 횟수 출력
bw.write("${d[n]}\n")
// 히스토리 출력
var cur = n
while (true) {
bw.write("$cur ")
if (cur == 1) break
cur = pre[cur]
}
bw.close()
}
'알고리즘&자료구조' 카테고리의 다른 글
| 정렬 알고리즘 활용 문제 풀이 (0) | 2023.02.07 |
|---|---|
| DP 문제 풀기 (0) | 2023.01.20 |
| kotlin 문자열 자르기 (0) | 2023.01.11 |
| 시뮬레이션 (0) | 2022.12.31 |
| 백트래킹 (0) | 2022.12.24 |
