μΆμ² : https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6
νλ€μ΄(μ β‘οΈ μλ)
κ³Ό 보ν
μ
(μλ β‘οΈ μ)
μΌλ‘ ꡬμ±λλ€.λμ κ³νλ²
μ΄λΌκ³ λ λΆλ¦°λ€.νλ€μ΄ VS 보ν μ
DP ν
μ΄λΈ
μ΄λΌκ³ λΆλ₯Έλ€.1. μ΅μ λΆλΆ ꡬ쑰 (Optimal Substructure)
ππ» ν° λ¬Έμ λ₯Ό μμ λ¬Έμ λ‘ λλ μ μμΌλ©° μμ λ¬Έμ μ λ΅μ λͺ¨μμ ν° λ¬Έμ λ₯Ό ν΄κ²°ν μ μλ€.
2. μ€λ³΅λλ λΆλΆ λ¬Έμ (Overlapping Subproblem)
ππ» λμΌν μμ λ¬Έμ λ₯Ό λ°λ³΅μ μΌλ‘ ν΄κ²°ν΄μΌ νλ€.
νΌλ³΄λμΉ μμ΄μ μ νμ(μΈμ ν νλ€ μ¬μ΄μ κ΄κ³μ)μΌλ‘ νννλ©΄ μλκ³Ό κ°λ€.
ππ» νλ‘κ·Έλλ°μμλ μ΄λ¬ν μμ΄μ λ°°μ΄
μ΄λ 리μ€νΈ
λ₯Ό μ΄μ©ν΄ νν
νΌλ³΄λμΉ μμ΄μ΄ κ³μ°λλ κ³Όμ μ μλμ κ°μ΄ ννν μ μλ€.
π€― μκ° λ³΅μ‘λ λΆμ
β
λ¨μ μ¬κ· ν¨μ
λ‘ νΌλ³΄λμΉ μμ΄μ ν΄κ²°νλ©΄ μ§μ μκ° λ³΅μ‘λ
λ₯Ό κ°μ§κ² λλ€.
β
nμ΄ μ‘°κΈλ§ μ»€μ Έλ κΈ°νκΈμμ μΌλ‘ λ§μ μκ°μ΄ νμν¨
β
λ€μκ³Ό κ°μ΄ f(2)κ° μ¬λ¬ λ² νΈμΆλλ κ²μ νμΈν μ μλ€. (μ€λ³΅λλ λΆλΆ λ¬Έμ )
β
νΌλ³΄λμΉ μμ΄μ μκ° λ³΅μ‘λλ μλμ κ°λ€.
λΉ
μ€ νκΈ°λ²μ κΈ°μ€μΌλ‘ f(30)μ κ³μ°νκΈ° μν΄ μ½ 10μ΅κ°λμ μ°μ°μ μνν΄μΌ νλ€. κ·Έλ λ€λ©΄ f(100)μ κ³μ°νκΈ° μν΄ μΌλ§λ λ§μ μ°μ°μ μνν΄μΌ ν κΉ β
ππ» f(30)κ³Όλ λΉκ΅λ μλκ² λ§μ μ°μ°μ ν΄μΌν κ²μ΄λ€.
λ¨Όμ , νΌλ³΄λμΉ μμ΄μ΄ λ€μ΄λλ―Ή νλ‘κ·Έλλ°μ μ¬μ© 쑰건μ λ§μ‘±νλμ§ νμΈνλ€.
1. `μ΅μ λΆλΆ ꡬ쑰` : ν° λ¬Έμ λ₯Ό μμ λ¬Έμ λ‘ λλ μ μμ΅λλ€.
2. `μ€λ³΅λλ λΆλΆ λ¬Έμ ` : λμΌν μμ λ¬Έμ λ₯Ό λ°λ³΅μ μΌλ‘ ν΄κ²°ν©λλ€.
ππ» νΌλ³΄λμΉ μμ΄μ λ€μ΄λλ―Ή νλ‘κ·Έλλ°μ μ¬μ© 쑰건μ λ§μ‘±ν©λλ€.
μΊμ±(Caching)
μ΄λΌκ³ λ ν©λλ€.μλ°ν λ§νλ©΄ λ©λͺ¨μ΄μ μ΄μ
μ μμ μ κ³μ°λ κ²°κ³Όλ₯Ό μΌμμ μΌλ‘ κΈ°λ‘ν΄ λλ λμ κ°λ
μ μλ―Ένλ€. λ°λΌμ λ©λͺ¨μ΄μ μ΄μ
μ λ€μ΄λλ―Ή νλ‘κ·Έλλ°μ κ΅νλ κ°λ
μ μλλ€. ν λ² κ³μ°λ κ²°κ³Όλ₯Ό λ΄μ λκΈ°λ§ νκ³ λ€μ΄λλ―Ή νλ‘κ·Έλλ°μ μν΄ νμ©νμ§ μμ μλ μλ€.
ππ» λ°λΌμ λ©λͺ¨μ΄μ μ΄μ
κ³Ό λ€μ΄λλ―Ή νλ‘κ·Έλλ°μ κ°μ κ°λ
μ΄ μλλ€!
[νλ€μ΄] λ©λͺ¨μ΄μ μ΄μ (Memoization) μμ€μ½λ
python
# ν λ² κ³μ°λ κ²°κ³Όλ₯Ό λ©λͺ¨μ΄μ μ΄μ (Memoization)νκΈ° μν 리μ€νΈ μ΄κΈ°ν d = [0] * 100 # νΌλ³΄λμΉ ν¨μ(Fibonacci Function)λ₯Ό μ¬κ·ν¨μλ‘ κ΅¬ν (νλ€μ΄ λ€μ΄λλ―Ή νλ‘κ·Έλλ°) def fibo(x): # μ’ λ£ μ‘°κ±΄(1 νΉμ 2μΌ λ 1μ λ°ν) if x == 1 or x == 2: return 1 # μ΄λ―Έ κ³μ°ν μ μλ λ¬Έμ λΌλ©΄ κ·Έλλ‘ λ°ν if d[x] != 0: return d[x] # μμ§ κ³μ°νμ§ μμ λ¬Έμ λΌλ©΄ μ νμμ λ°λΌμ νΌλ³΄λμΉ κ²°κ³Ό λ°ν d[x] = fibo(x - 1) + fibo(x - 2) return d[x] print(fibo(99))
Java
import java.util.*; public class Main { // ν λ² κ³μ°λ κ²°κ³Όλ₯Ό λ©λͺ¨μ΄μ μ΄μ (Memoization)νκΈ° μν λ°°μ΄ μ΄κΈ°ν public static long[] d = new long[100]; // νΌλ³΄λμΉ ν¨μ(Fibonacci Function)λ₯Ό μ¬κ·ν¨μλ‘ κ΅¬ν (νλ€μ΄ λ€μ΄λλ―Ή νλ‘κ·Έλλ°) public static long fibo(int x) { // μ’ λ£ μ‘°κ±΄(1 νΉμ 2μΌ λ 1μ λ°ν) if (x == 1 || x == 2) { return 1; } // μ΄λ―Έ κ³μ°ν μ μλ λ¬Έμ λΌλ©΄ κ·Έλλ‘ λ°ν if (d[x] != 0) { return d[x]; } // μμ§ κ³μ°νμ§ μμ λ¬Έμ λΌλ©΄ μ νμμ λ°λΌμ νΌλ³΄λμΉ κ²°κ³Ό λ°ν d[x] = fibo(x - 1) + fibo(x - 2); return d[x]; } public static void main(String[] args) { System.out.println(fibo(50)); } }
π€― μκ° λ³΅μ‘λ λΆμ
λ©λͺ¨μ΄μ μ΄μ
μ μ΄μ©νλ κ²½μ° νΌλ³΄λμΉ μμ΄ ν¨μμ μκ° λ³΅μ‘λλ 0(N)
μ΄λ€.
[보ν μ ] λ€μ΄λλ―Ή νλ‘κ·Έλλ° μμ€μ½λ
python
# μμ κ³μ°λ κ²°κ³Όλ₯Ό μ μ₯νκΈ° μν DP ν μ΄λΈ μ΄κΈ°ν d = [0] * 100 # 첫 λ²μ§Έ νΌλ³΄λμΉ μμ λ λ²μ§Έ νΌλ³΄λμΉ μλ 1 d[1] = 1 d[2] = 1 n = 99 # νΌλ³΄λμΉ ν¨μ(Fibonacci Function) λ°λ³΅λ¬ΈμΌλ‘ ꡬν(보ν μ λ€μ΄λλ―Ή νλ‘κ·Έλλ°) for i in range(3, n + 1): d[i] = d[i - 1] + d[i - 2] print(d[n])
Java
import java.util.*; public class Main { public static long[] d = new long[100]; public static void main(String[] args) { // 첫 λ²μ§Έ νΌλ³΄λμΉ μμ λ λ²μ§Έ νΌλ³΄λμΉ μλ 1 d[1] = 1; d[2] = 1; int n = 50; // 50λ²μ§Έ νΌλ³΄λμΉ μλ₯Ό κ³μ° // νΌλ³΄λμΉ ν¨μ(Fibonacci Function) λ°λ³΅λ¬ΈμΌλ‘ ꡬν(보ν μ λ€μ΄λλ―Ή νλ‘κ·Έλλ°) for (int i = 3; i <= n; i++) { d[i] = d[i - 1] + d[i - 2]; } System.out.println(d[n]); } }
μ΅μ λΆλΆ ꡬ쑰
λ₯Ό κ°μ§ λ μ¬μ©ν μ μμ΅λλ€.μ΅μ λΆλΆ ꡬ쑰
: ν° λ¬Έμ λ₯Ό μμ λ¬Έμ λ‘ λλ μ μμΌλ©° μμ λ¬Έμ μ λ΅μ λͺ¨μμ ν° λ¬Έμ λ₯Ό ν΄κ²°ν μ μλ μν©λΆλΆ λ¬Έμ μ μ€λ³΅
μ
λλ€.λΆν μ 볡μ λνμ μΈ μμμΈ ν΅ μ λ ¬μ μ΄ν΄λ³΄μ
κΈ°μ€ μμ(Pivot)
κ° μ리λ₯Ό λ³κ²½ν΄μ μ리λ₯Ό μ‘μΌλ©΄ κ·Έ κΈ°μ€ μμμ μμΉλ λ°λμ§ μλλ€.그리λ
, ꡬν
, μμ νμ
λ±μ μμ΄λμ΄λ‘ λ¬Έμ λ₯Ό ν΄κ²°ν μ μλμ§ κ²ν ν΄λ³΄κ³ νμ΄ λ°©λ²μ΄ λ μ€λ₯΄μ§ μμΌλ©΄ λ€μ΄λλ―Ή νλ‘κ·Έλλ°
μ κ³ λ €ν΄ λ³΄μa, = 1λ²μ§Έ μλμ°½κ³ κΉμ§μ μ΅μ μ ν΄ (μ»μ μ μλ μλμ μ΅λκ°)μ΄λΌκ³ μ μνλ€λ©΄ λ€μ΄λλ―Ή νλ‘κ·Έλλ°μ μ μ©ν μ μλ€.
μΌμͺ½λΆν° μ°¨λ‘λλ‘ μλμ°½κ³ λ₯Ό ν΄λ€κ³ νμ λ, νΉμ ν λ²μ§Έμ μλμ°½κ³ μ λν΄μ νΈμ§ μ νΈμ§μ μ¬λΆλ₯Ό κ²°μ νλ©΄, μλ 2κ°μ§ κ²½μ° μ€μμ λ λ§μ μλμ νΈ μ μλ κ²½μ°λ₯Ό μ ννλ©΄ λλ€.
μ΄λ₯Ό μμμΌλ‘ νννλ©΄
μ νμμ μλμ κ°λ€
ππ» iλ²μ§Έ κΉμ§ μ»μ μ μλ μλμ μ΅λκ°μ i-1λ²μ§ΈκΉμ§μ μ΅λκ°
κ³Ό i-2λ²μ§ΈκΉμ§μ μ΅λκ° + νμ¬ μ°½κ³ μ μλκ°
μ€ λ ν° κ°μ΄λ€.
ν μΉΈ μ΄μ λ¨μ΄μ§ μλμ°½κ³ λ νμ νΈ μ μμΌλ―λ‘ (i - 3)λ²μ§Έ μ΄νλ κ³ λ €ν νμκ° μλ€.
python
# μ μ Nμ μ λ ₯ λ°κΈ° n = int(input()) # λͺ¨λ μλ μ 보 μ λ ₯ λ°κΈ° array = list(map(int, input().split())) # μμ κ³μ°λ κ²°κ³Όλ₯Ό μ μ₯νκΈ° μν DP ν μ΄λΈ μ΄κΈ°ν d = [0] * 100 # nμ μ΅λ 100κΉμ§ λ€μ΄μ¬ μ μλ€νμΌλ―λ‘ # λ€μ΄λλ―Ή νλ‘κ·Έλλ°(Dynamic Programming) μ§ν (보ν μ ) d[0] = array[0] d[1] = max(array[0], array[1]) for i in range(2, n): d[i] = max(d[i - 1], d[i - 2] + array[i]) # κ³μ°λ κ²°κ³Ό μΆλ ₯ print(d[n - 1])
Java
import java.util.*; public class Main { // μμ κ³μ°λ κ²°κ³Όλ₯Ό μ μ₯νκΈ° μν DP ν μ΄λΈ μ΄κΈ°ν public static int[] d = new int[100]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); // μ μ Nμ μ λ ₯λ°κΈ° int n = sc.nextInt(); // λͺ¨λ μλ μ 보 μ λ ₯λ°κΈ° int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } // λ€μ΄λλ―Ή νλ‘κ·Έλλ°(Dynamic Programming) μ§ν(보ν μ ) d[0] = arr[0]; d[1] = Math.max(arr[0], arr[1]); for (int i = 2; i < n; i++) { d[i] = Math.max(d[i - 1], d[i - 2] + arr[i]); } // κ³μ°λ κ²°κ³Ό μΆλ ₯ System.out.println(d[n - 1]); } }
μ΅μ λΆλΆ ꡬ쑰
λ₯Ό λ§μ‘±νλ€.νΌλ³΄λμΉ μμ΄ λ¬Έμ λ₯Ό λμνν κ²μ²λΌ ν¨μκ° νΈμΆλλ κ³Όμ μ κ·Έλ¦ΌμΌλ‘ κ·Έλ €λ³΄λ©΄ μλκ³Ό κ°λ€.
β
μ΅μ λΆλΆ ꡬ쑰
μ μ€λ³΅λλ λΆλΆ λ¬Έμ
λ₯Ό λ§μ‘±νλ€.
μλ₯Ό λ€μ΄ xκ° 6μΌ λλ 6μμ 1μ λΊ f(5)
μμμ μ΅μ μ ν΄, 6μμ 2λ₯Ό λλ f(3)
μμμ μ΅μ μ ν΄, 6μμ 3μ λλ f(2)
μμμ μ΅μ μ ν΄ μ€μμ κ°μ₯ μμ κ°μ κ³¨λΌ f(6)μΌ λμ μ΅μ μ ν΄λ₯Ό ꡬν μ μλ€.
λ€λ§ μ¬κΈ°μ 6μ 5λ‘ λλμ΄λ¨μ΄μ§μ§ μκΈ° λλ¬Έμ 5λ‘ λλλ κ²½μ°λ κ³ λ €νμ§ μμλ€.
iλ²μ§Έ a = iλ₯Ό 1λ‘ λ§λ€κΈ° μν μ΅μ μ°μ° νμλΌκ³ μ μ νμ λ, μ νμμ μλμ κ°λ€.
λ¨, 1μ λΉΌλ μ°μ°μ μ μΈνκ³ λ ν΄λΉ μλ‘ λλμ΄λ¨μ΄μ§ λμ νν΄
μ νμμ μ μ©ν μ μλ€.
python
# μ μ Xλ₯Ό μ λ ₯ λ°κΈ° x = int(input()) # μμ κ³μ°λ κ²°κ³Όλ₯Ό μ μ₯νκΈ° μν DP ν μ΄λΈ μ΄κΈ°ν d = [0] * 1000001 # λ€μ΄λλ―Ή νλ‘κ·Έλλ°(Dynamic Programming) μ§ν(보ν μ ) for i in range(2, x + 1): # νμ¬μ μμμ 1μ λΉΌλ κ²½μ° d[i] = d[i - 1] + 1 # νμ¬μ μκ° 2λ‘ λλμ΄ λ¨μ΄μ§λ κ²½μ° if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) # νμ¬μ μκ° 3μΌλ‘ λλμ΄ λ¨μ΄μ§λ κ²½μ° if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) # νμ¬μ μκ° 5λ‘ λλμ΄ λ¨μ΄μ§λ κ²½μ° if i % 5 == 0: d[i] = min(d[i], d[i // 5] + 1) print(d[x])
python(μ§μ.ver)
x = int(input()) dp = [0] * (x + 1) for i in range(2, x + 1): arr = [] if i % 2 == 0: arr.append(dp[i//2]) if i % 3 == 0: arr.append(dp[i//3]) if i % 5 == 0: arr.append(dp[i//5]) arr.append(dp[i-1]) dp[i] = int(min(arr)) + 1 print(dp[x])
Java
import java.util.*; public class Main { // μμ κ³μ°λ κ²°κ³Όλ₯Ό μ μ₯νκΈ° μν DP ν μ΄λΈ μ΄κΈ°ν public static int[] d = new int[30001]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int x = sc.nextInt(); // λ€μ΄λλ―Ή νλ‘κ·Έλλ°(Dynamic Programming) μ§ν(보ν μ ) for (int i = 2; i <= x; i++) { // νμ¬μ μμμ 1μ λΉΌλ κ²½μ° d[i] = d[i - 1] + 1; // νμ¬μ μκ° 2λ‘ λλμ΄ λ¨μ΄μ§λ κ²½μ° if (i % 2 == 0) d[i] = Math.min(d[i], d[i / 2] + 1); // νμ¬μ μκ° 3μΌλ‘ λλμ΄ λ¨μ΄μ§λ κ²½μ° if (i % 3 == 0) d[i] = Math.min(d[i], d[i / 3] + 1); // νμ¬μ μκ° 5λ‘ λλμ΄ λ¨μ΄μ§λ κ²½μ° if (i % 5 == 0) d[i] = Math.min(d[i], d[i / 5] + 1); } System.out.println(d[x]); } }
λ¬Έμ ν΄κ²° μμ΄λμ΄
N = 3, M = 7μ΄κ³ , κ° ννμ λ¨μκ° 2, 3, 5μΈ κ²½μ°λ₯Ό νμΈν΄ 보μ
1οΈβ£ [Step 1 (μ΄κΈ°ν)]
INF(무ν)
μ κ°μ μ€μ INF
μ νΉμ κΈμ‘μ λ§λ€ μ μλ νν ꡬμ±μ΄ κ°λ₯νμ§ μλ€λ μλ―Έλ₯Ό κ°μ§λ€.2οΈβ£ [Step 2]
3οΈβ£ [Step 3]
4οΈβ£ [Step 4]
python
# μ μ N, Mμ μ λ ₯ λ°κΈ° n, m = map(int, input().split()) # Nκ°μ νν λ¨μ μ 보λ₯Ό μ λ ₯ λ°κΈ° array = [] for i in range(n): array.append(int(input())) # ν λ² κ³μ°λ κ²°κ³Όλ₯Ό μ μ₯νκΈ° μν DP ν μ΄λΈ μ΄κΈ°ν d = [10001] * (m + 1) # λ€μ΄λλ―Ή νλ‘κ·Έλλ°(Dynamic Programming) μ§ν(보ν μ ) d[0] = 0 for i in range(n): # i = νν λ¨μ for j in range(array[i], m + 1): # j = κΈμ‘ if d[j - array[i]] != 10001: # (i - k)μμ λ§λλ λ°©λ²μ΄ μ‘΄μ¬νλ κ²½μ° d[j] = min(d[j], d[j - array[i]] + 1) # κ³μ°λ κ²°κ³Ό μΆλ ₯ if d[m] == 10001: # μ΅μ’ μ μΌλ‘ Mμμ λ§λλ λ°©λ²μ΄ μλ κ²½μ° print(-1) else: print(d[m])
Java
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // μ μ N, Mμ μ λ ₯λ°κΈ° int n = sc.nextInt(); int m = sc.nextInt(); // Nκ°μ νν λ¨μ μ 보λ₯Ό μ λ ₯ λ°κΈ° int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } // μμ κ³μ°λ κ²°κ³Όλ₯Ό μ μ₯νκΈ° μν DP ν μ΄λΈ μ΄κΈ°ν int[] d = new int[m + 1]; Arrays.fill(d, 10001); // λ€μ΄λλ―Ή νλ‘κ·Έλλ°(Dynamic Programming) μ§ν(보ν μ ) d[0] = 0; for (int i = 0; i < n; i++) { for (int j = arr[i]; j <= m; j++) { // (i - k)μμ λ§λλ λ°©λ²μ΄ μ‘΄μ¬νλ κ²½μ° if (d[j - arr[i]] != 10001) { d[j] = Math.min(d[j], d[j - arr[i]] + 1); } } } // κ³μ°λ κ²°κ³Ό μΆλ ₯ if (d[m] == 10001) { // μ΅μ’ μ μΌλ‘ Mμμ λ§λλ λ°©λ²μ΄ μλ κ²½μ° System.out.println(-1); } else { System.out.println(d[m]); } } }
λ¬Έμ ν΄κ²° μμ΄λμ΄
μ νμμ μλμ κ°λ€.
dp[i][j] = array[i][j] + max(dp[i - 1][j - 1], dp[i][j - 1], dp[i + 1][j - 1])
μ΄λ ν μ΄λΈμ μ κ·Όν λλ§λ€ 리μ€νΈμ λ²μλ₯Ό λ²μ΄λμ§ μλμ§ μ²΄ν¬ν΄μΌ νλ€.
νΈμμ μ΄κΈ° λ°μ΄ν°λ₯Ό λ΄λ λ³μ arrayλ₯Ό μ¬μ©νμ§ μκ³ λ°λ‘ DP ν μ΄λΈμ μ΄κΈ° λ°μ΄ν°λ₯Ό λ΄μμ λ€μ΄λλ―Ή νλ‘κ·Έλλ°μ μ μ©ν μ μλ€.
ν΄κ²° κ³Όμ
python
# ν μ€νΈ μΌμ΄μ€(Test Case) μ λ ₯ for tc in range(int(input())): # κΈκ΄ μ 보 μ λ ₯ n, m = map(int, input().split()) array = list(map(int, input().split())) # λ€μ΄λλ―Ή νλ‘κ·Έλλ°μ μν 2μ°¨μ DP ν μ΄λΈ μ΄κΈ°ν dp = [] index = 0 for i in range(n): # 0 ~ 3, 4 ~ 7 μ΄λ κ² μ¬λΌμ΄μ± νμ¬ DP μ΄κΈ°ν dp.append(array[index:index + m]) index += m # 4, 8, 12 μ΄λ κ² μ¦κ° # λ€μ΄λλ―Ή νλ‘κ·Έλλ° μ§ν for j in range(1, m): for i in range(n): # μΌμͺ½ μμμ μ€λ κ²½μ° if i == 0: # μΈλ±μ€ λ²μ΄λ κ²½μ° left_up = 0 else: left_up = dp[i - 1][j - 1] # μΌμͺ½ μλμμ μ€λ κ²½μ° if i == n - 1: # μΈλ±μ€ λ²μ΄λ κ²½μ° left_down = 0 else: left_down = dp[i + 1][j - 1] # μΌμͺ½μμ μ€λ κ²½μ° left = dp[i][j - 1] dp[i][j] = dp[i][j] + max(left_up, left_down, left) result = 0 # λ§μ§λ§ νμ μ΄(κ°μ₯ μ€λ₯Έμͺ½ μ΄) μ€ μ΅λκ° κ³ λ₯΄κΈ° for i in range(n): result = max(result, dp[i][m - 1]) print(result)
Java
import java.util.*; public class Main { static int testCase, n, m; static int[][] arr = new int[20][20]; static int[][] dp = new int[20][20]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); // ν μ€νΈ μΌμ΄μ€(Test Case) μ λ ₯ testCase = sc.nextInt(); for (int tc = 0; tc < testCase; tc++) { // κΈκ΄ μ 보 μ λ ₯ n = sc.nextInt(); m = sc.nextInt(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { arr[i][j] = sc.nextInt(); } } // λ€μ΄λλ―Ή νλ‘κ·Έλλ°μ μν 2μ°¨μ DP ν μ΄λΈ μ΄κΈ°ν for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { dp[i][j] = arr[i][j]; } } // λ€μ΄λλ―Ή νλ‘κ·Έλλ° μ§ν for (int j = 1; j < m; j++) { for (int i = 0; i < n; i++) { int leftUp, leftDown, left; // μΌμͺ½ μμμ μ€λ κ²½μ° if (i == 0) leftUp = 0; else leftUp = dp[i - 1][j - 1]; // μΌμͺ½ μλμμ μ€λ κ²½μ° if (i == n - 1) leftDown = 0; else leftDown = dp[i + 1][j - 1]; // μΌμͺ½μμ μ€λ κ²½μ° left = dp[i][j - 1]; dp[i][j] = dp[i][j] + Math.max(leftUp, Math.max(leftDown, left)); } } int result = 0; for (int i = 0; i < n; i++) { result = Math.max(result, dp[i][m - 1]); } System.out.println(result); } } }
λ¬Έμ ν΄κ²° μμ΄λμ΄
D[i] = array[i]λ₯Ό λ§μ§λ§ μμλ‘ κ°μ§λ λΆλΆ μμ΄μ μ΅λ κΈΈμ΄
μ νμμ μλμ κ°λ€.
λ¬Έμ ν΄κ²° κ³Όμ
κ°μ₯ λ¨Όμ μ
λ ₯ λ°μ λ³μ¬ μ 보μ μμλ₯Ό λ€μ§λλ€.
κ°μ₯ κΈ΄ μ¦κ°νλ λΆλΆ μμ΄ (LIS) μκ³ λ¦¬μ¦μ μννμ¬ μ λ΅μ λμΆνλ€.
python
n = int(input()) array = list(map(int, input().split())) # μμλ₯Ό λ€μ§μ΄ 'μ΅μ₯ μ¦κ° λΆλΆ μμ΄' λ¬Έμ λ‘ λ³ν array.reverse() # λ€μ΄λλ―Ή νλ‘κ·Έλλ°μ μν 1μ°¨μ DP ν μ΄λΈ μ΄κΈ°ν dp = [1] * n # κ°μ₯ κΈ΄ μ¦κ°νλ λΆλΆ μμ΄(LIS) μκ³ λ¦¬μ¦ μν for i in range(1, n): for j in range(0, i): if array[j] < array[i]: dp[i] = max(dp[i], dp[j] + 1) # μ΄μΈν΄μΌ νλ λ³μ¬μ μ΅μ μλ₯Ό μΆλ ₯ print(n - max(dp))
Java
import java.util.*; public class Main { static int n; static ArrayList<Integer> v = new ArrayList<Integer>(); static int[] dp = new int[2000]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); for (int i = 0; i < n; i++) { v.add(sc.nextInt()); } // μμλ₯Ό λ€μ§μ΄ 'μ΅μ₯ μ¦κ° λΆλΆ μμ΄' λ¬Έμ λ‘ λ³ν Collections.reverse(v); // λ€μ΄λλ―Ή νλ‘κ·Έλλ°μ μν 1μ°¨μ DP ν μ΄λΈ μ΄κΈ°ν for (int i = 0; i < n; i++) { dp[i] = 1; } // κ°μ₯ κΈ΄ μ¦κ°νλ λΆλΆ μμ΄(LIS) μκ³ λ¦¬μ¦ μν for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (v.get(j) < v.get(i)) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } // μ΄μΈν΄μΌ νλ λ³μ¬μ μ΅μ μλ₯Ό μΆλ ₯ int maxValue = 0; for (int i = 0; i < n; i++) { maxValue = Math.max(maxValue, dp[i]); } System.out.println(n - maxValue); } }