Dynamic Programming
ν° λ¬Έμ λ₯Ό μμ λ¬Έμ λ‘ λλ μ νΈλ μκ³ λ¦¬μ¦μ΄λ€.
Overlapping Subproblem (κ²ΉμΉλ λΆλΆλ¬Έμ )
Optimal Substructure(λ¬Έμ μ μ λ΅μ μμ λΆλΆμμ μ μ μμ λ) : μμ λ¬Έμ μμ ꡬν μ λ΅μ κ·Έκ²μ ν¬ν¨νλ ν° λ¬Έμ μμλ λμΌνλ€.
μ΄ λκ°μ§ μμ±μ λ§μ‘±ν΄μΌ λ€μ΄λλ―Ή νλ‘κ·Έλλ°μΌλ‘ λ¬Έμ λ₯Ό ν μ μλ€.
Overlapping Subproblem
λ¬Έμ : Nλ²μ§Έ νΌλ³΄λμΉ μλ₯Ό ꡬνλ λ¬Έμ
μμλ¬Έμ : N-1λ²μ§Έ νΌλ³΄λμΉ μλ₯Ό ꡬνλ λ¬Έμ , N-2λ²μ§Έ νΌλ³΄λμΉ μλ₯Ό ꡬνλ λ¬Έμ
λ¬Έμ : N-1λ²μ§Έ νΌλ³΄λμΉ μλ₯Ό ꡬνλ λ¬Έμ
μμλ¬Έμ : N-2λ²μ§Έ νΌλ³΄λμΉ μλ₯Ό ꡬνλ λ¬Έμ , N-3λ²μ§Έ νΌλ³΄λμΉ μλ₯Ό ꡬνλ λ¬Έμ
λ¬Έμ : N-2λ²μ§Έ νΌλ³΄λμΉ μλ₯Ό ꡬνλ λ¬Έμ
μμλ¬Έμ : N-3λ²μ§Έ νΌλ³΄λμΉ μλ₯Ό ꡬνλ λ¬Έμ , N-3λ²μ§Έ νΌλ³΄λμΉ μλ₯Ό ꡬνλ λ¬Έμ
μμ λ¬Έμ κ° κ²Ήμ³μΌνλ€. ν° λ¬Έμ μ μμ λ¬Έμ λ μλμ μ΄λ€.
ν° λ¬Έμ μ μμ λ¬Έμ λ₯Ό κ°μ λ°©λ²μΌλ‘ ν μ μλ€.
λ¬Έμ λ₯Ό μμ λ¬Έμ λ‘ μͺΌκ°€ μ μλ€.
Optimal Substructure
λ¬Έμ μ μ λ΅μ μμ λ¬Έμ μ μ λ΅μμ ꡬν μ μλ€.
N-1λ²μ§Έ νΌλ³΄λμΉ μλ₯Ό ꡬνλ λ¬Έμ = N-2λ²μ§Έ νΌλ³΄λμΉ μλ₯Ό ꡬνλ λ¬Έμ + N-3λ²μ§Έ νΌλ³΄λμΉ μλ₯Ό ꡬνλ λ¬Έμ
λ€μ΄λλ―Ή νλ‘κ·Έλλ°
κ° λ¬Έμ λ νλ²λ§ νμ΄μΌ νλ€.
κ°μ λ¬Έμ λ ꡬν λλ§λ€ μ λ΅μ΄ κ°λ€.(Optimal Substructure)
μ λ΅μ ꡬνμΌλ©΄, μ λ΅μ μ΄λκ°μ λ©λͺ¨ν΄λλλ€.(λ°°μ΄)=>Memoization
Top-down
λ¬Έμ λ₯Ό μμ λ¬Έμ λ‘ λλλ€.
μμ λ¬Έμ λ₯Ό νΌλ€.
μμ λ¬Έμ λ₯Ό νμμΌλ, μ΄μ λ¬Έμ λ₯Ό νΌλ€.
μ¬κ·νΈμΆμ μ΄μ©ν΄μ λ¬Έμ λ₯Ό μ½κ² ν μ μλ€. μκ°λ³΅μ‘λλ μ±μμΌνλ μΉΈμ μ X ν μΉΈμ μ±μ°λ 볡μ‘λ(ν¨μνλμ μκ° λ³΅μ‘λ)μ΄λ€.
Bottom-up
λ¬Έμ λ₯Ό ν¬κΈ°κ° μμ λ¬Έμ λΆν° μ°¨λ‘λλ‘ νΌλ€.
λ¬Έμ μ ν¬κΈ°λ₯Ό μ‘°κΈμ© ν¬κ² λ§λ€λ©΄μ λ¬Έμ λ₯Ό νΌλ€.
μμ λ¬Έμ λ₯Ό νλ©΄μ μκΈ° λλ¬Έμ, ν° λ¬Έμ λ νμ ν μ μλ€.
memoizationμ ν λ 무μμ κΈ°λ‘ν΄μΌν μ§ μ μνλ κ²μ΄ μ΅μ°μ μ΄λ€.
Top-down(memorization) λ°©μμ 'νν₯μ'μ΄λΌκ³ λ νλ©°, bottom-up λ°©μμ 'μν₯μ'μ΄λΌκ³ λ νλ€. DPμ μ νμ μΈ ννλ bottom-up λ°©μμ΄λ€.
Bottom-up λ°©μμμ μ¬μ©λλ κ²°κ³Ό μ μ₯μ© λ¦¬μ€νΈ(λ°°μ΄)λ DP ν μ΄λΈ μ΄λΌ λΆλ₯΄λ©°, memorizationμ Top-down λ°©μμ κ΅νλμ΄ μ¬μ©λλ ννμ΄λ€.
μ€μ΅
1λ‘ λ§λ€κΈ°
D[N] = Nμ 1λ‘ λ§λλλ° νμν μ°μ°μ μ΅μκ° 1. Nμ΄ 3μΌλ‘ λλμ΄ λ¨μ΄μ§λ©΄, 3μΌλ‘ λλλ€. D[N/3]+1
2. Nμ΄ 2λ‘ λλμ΄ λ¨μ΄μ§λ©΄, 2λ‘ λλλ€. D[N/2]+1
3. 1μ λΊλ€. D[N-1]+1
=> D[N]=min(1,2,3)
top-down
bottom-up
2Xn νμΌλ§
2Xn μ§μ¬κ°νμ 1x2,2x1νμΌλ‘ μ±μ°λ λ°©λ²μ μ => D[n]=2xiμ§μ¬κ°νμ μ±μ°λ λ°©λ²μ μ => D[n]=D[n-1]+D[n-2]
μ΄ λ, n=0μΌ λλ κ²½μ°μ μμ΄κΈ° λλ¬Έμ 1μ μΆλ ₯νλ€.
bottom-up
2xn νμΌλ§ 2
2Xn μ§μ¬κ°νμ 1x2,2x1,2x2νμΌλ‘ μ±μ°λ λ°©λ²μ μ => D[n]=2xiμ§μ¬κ°νμ μ±μ°λ λ°©λ²μ μ => D[n]=D[n-1]+2*D[n-2]
bottom-up
1,2,3 λνκΈ°
μ μ nμ 1,2,3μ μ‘°ν©μΌλ‘ λνλ΄λ λ°©λ²μ μλ₯Ό ꡬνλ λ¬Έμ => D[n]=μ μ nμ 1,2,3μ μ‘°ν©μΌλ‘ λνλ΄λ λ°©λ²μ μ => λ§μ§λ§μ μ€λ μκ° μ€μνλ€. => D[n]=D[n-1]+D[n-2]+D[n-3]
bottom-up
λΆμ΄λΉ΅ ν맀νκΈ°
λΆμ΄λΉ΅ iκ°λ₯Ό νμμ μ»μ μ μλ μμ΅ P[i]μΌ λ, Nκ°λ₯Ό λͺ¨λ ν맀ν΄μ μ»μ μ μλ μ΅λ μμ΅κ΅¬νκΈ° => D[n]=nκ°λ₯Ό λͺ¨λ ν맀ν΄μ μ»μ μ μλ μ΅λμμ΅
λΆμ΄λΉ΅ μ
κ°κ²©
λ¨μ λΆμ΄λΉ΅μ μ
μ΅λμμ΅ κ°λ₯ν κ²½μ°
1
P[1]
n-1
P[1]+D[n-1]
2
P[2]
n-2
P[2]+D[n-2]
...
...
...
...
n-1
P[n-1]
1
P[n-1]+D[1]
n
P[n]
0
P[n]+D[0]
=> D[n] = max(P[i]+D[n-i])(1<=i<=n)
μ¬μ΄ κ³λ¨ μ
μΈμ ν μ리μ μ°¨μ΄κ° 1μ΄ λλ μλ₯Ό κ³λ¨ μλΌκ³ νλ€. ex)45656 κΈΈμ΄κ° NμΈ κ³λ¨ μμ κ°μλ₯Ό ꡬνμ¬λΌ.(0μΌλ‘ μμνλ μλ μλ€.)
=> D[N][L]=Nμ리 κ³λ¨μ, λ§μ§λ§ μ L L -> L+1 or L-1 => D[N][L]=D[N-1][L-1]+D[N-1]+D[L+1]
μ€λ₯΄λ§ μ
μ€λ₯΄λ§ μλ μμ μλ¦¬κ° μ€λ¦μ°¨μμ μ΄λ£¨λ μλ₯Ό λ§νλ€. μ΄ λ, μΈμ ν μκ° κ°μλ μ€λ¦μ°¨μμΌλ‘ μΉλ€. μλ₯Ό λ€μ΄, 2234μ 3678, 11119λ μ€λ₯΄λ§ μμ΄μ§λ§, 2232, 3676, 91111μ μ€λ₯΄λ§ μκ° μλλ€. μμ κΈΈμ΄ Nμ΄ μ£Όμ΄μ‘μ λ, μ€λ₯΄λ§ μμ κ°μλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€. μλ 0μΌλ‘ μμν μ μλ€.
=> D[N][L]=Nμ리 μ€λ₯΄λ§μ, λ§μ§λ§μ L => D[N][L]=sum(D[N-1][k])(0<=k<=L)
μ΄μΉμ
0κ³Ό 1λ‘λ§ μ΄λ£¨μ΄μ§ μλ₯Ό μ΄μ§μλΌ νλ€. μ΄λ¬ν μ΄μ§μ μ€ νΉλ³ν μ±μ§μ κ°λ κ²λ€μ΄ μλλ°, μ΄λ€μ μ΄μΉμ(pinary number)λΌ νλ€. μ΄μΉμλ λ€μμ μ±μ§μ λ§μ‘±νλ€.
μ΄μΉμλ 0μΌλ‘ μμνμ§ μλλ€.
μ΄μΉμμμλ 1μ΄ λ λ² μ°μμΌλ‘ λνλμ§ μλλ€. μ¦, 11μ λΆλΆ λ¬Έμμ΄λ‘ κ°μ§ μλλ€.
μλ₯Ό λ€λ©΄ 1, 10, 100, 101, 1000, 1001 λ±μ΄ μ΄μΉμκ° λλ€. νμ§λ§ 0010101μ΄λ 101101μ κ°κ° 1, 2λ² κ·μΉμ μλ°°λλ―λ‘ μ΄μΉμκ° μλλ€.
=> D[n]=D[n-1]+D[n-2] (nμ리 2μΉμ = nλ²μ§Έ μ리μ 0+nλ²μ§Έ μ리μ 1)
μ€ν°μ»€
μ€ν°μ»€ 2nκ°κ° 2Xnλͺ¨μμΌλ‘ λ°°μΉλμ΄μλ€. μ€ν°μ»€ ν μ₯μ λΌλ©΄ λ³μ 곡μ νλ μ€ν°μ»€λ λͺ¨λ μ°’μ΄μ Έμ μ¬μ©ν μ μλ€. μ μμ ν©μ μ΅λλ‘ λ§λλ λ¬Έμ . μ¦, 2nκ°μ μ€ν°μ»€ μ€μμ μ μμ ν©μ΄ μ΅λκ° λλ©΄μ μλ‘ λ³μ 곡μ νμ§ μλ μ€ν°μ»€ μ§ν©μ ꡬν΄μΌ νλ€.
=> D[n][s]=2Xn μ€ν°μ»€ μν s
s = 0μ λ―μ§ μμ
D[n][0]=n-1μ΄μμ μ€ν°μ»€λ₯Ό μ΄λ»κ² λ―μλμ§ μκ΄μ΄ μλ€. =>
max(D[n-1][0],D[n-1][1],D[n-1][2])
s = 1μ μμͺ½ μ€ν°μ»€ λ―μ
D[n][1]= n-1μ΄μ μμͺ½ μ€ν°μ»€λ λ―μΌλ©΄ μλ¨.
max(D[n-1][0],D[n-1][2])+A[n][0]
s = 2λ μλμͺ½ μ€ν°μ»€ λ―μ
D[n][1]= n-1μ΄μ μλμͺ½ μ€ν°μ»€λ λ―μΌλ©΄ μλ¨.
max(D[n-1][0],D[n-1][1])+A[n][1]
=> max(D[n][0],D[n][1],D[n][2])
ν¬λμ£Όμμ
ν¬λμ£Ό μμ μ ννλ©΄ κ·Έ μμ λ€μ΄μλ ν¬λμ£Όλ λͺ¨λ λ§μ μΌ νκ³ , λ§μ νμλ μλ μμΉμ λ€μ λμμΌ νλ€.
μ°μμΌλ‘ λμ¬ μλ 3μμ λͺ¨λ λ§μ€ μλ μλ€.
1λΆν° nκΉμ§μ λ²νΈκ° λΆμ΄ μλ nκ°μ ν¬λμ£Ό μμ΄ μμλλ‘ ν μ΄λΈ μμ λμ¬ μκ³ , κ° ν¬λμ£Ό μμ λ€μ΄μλ ν¬λμ£Όμ μμ΄ μ£Όμ΄μ‘μ λ, κ°μ₯ λ§μ μμ ν¬λμ£Όλ₯Ό λ§μ€ μ μλλ‘ νλ νλ‘κ·Έλ¨μ μμ±νμμ€.
D[i][j] = A[1]~A[n]κΉμ§ ν¬λμ£Όλ₯Ό λ§μ §μ λ λ§μ€ μ μλ ν¬λμ£Όμ μ΅λ μ
0λ²μ°μ : A[i]λ₯Ό λ§μμ§ μμ
max(D[i-1][0],D[i-1][1],D[i-1][2])
1λ²μ°μ : A[i-1]μ λ§μμ§ μμ.
D[i-1][0]+A[i]
2λ²μ°μ : A[i-1]λ§μκ³ , A[i-2]λ§μμ§ μμ
D[i-1][1]+A[i]
D[i] = A[1]~A[n]κΉμ§ ν¬λμ£Όλ₯Ό λ§μ §μ λ λ§μ€ μ μλ ν¬λμ£Όμ μ΅λ μ
0λ²μ°μ : A[i]λ₯Ό λ§μμ§ μμ
D[i-1]
1λ²μ°μ : A[i-1]μ λ§μμ§ μμ.
D[i-2]+A[i]
2λ²μ°μ : A[i-1]λ§μκ³ , A[i-2]λ§μμ§ μμ
D[i-3]+A[i-1]+A[i]
=> D[i]=max(D[i-1], D[i-2]+A[i], D[i-3]+A[i-1]+A[i])
κ°μ₯ κΈ΄ μ¦κ°νλ λΆλΆ μμ΄
μμ΄ Aκ° μ£Όμ΄μ‘μ λ, κ°μ₯ κΈ΄ μ¦κ°νλ λΆλΆ μμ΄μ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
μ) μμ΄ A = {10, 20, 10, 30, 20, 50} μΈ κ²½μ°μ κ°μ₯ κΈ΄ μ¦κ°νλ λΆλΆ μμ΄μ A = {10, 20, 10, 30, 20, 50} μ΄κ³ , κΈΈμ΄λ 4μ΄λ€.
D[i]= A[1]~A[n]κΉμ§ μμ΄μ΄ μμ λ, A[i]λ₯Ό λ§μ§λ§μΌλ‘ νλ κ°μ₯ κΈ΄ μ¦κ°νλ λΆλΆ μμ΄μ κΈΈμ΄(A[i]λ₯Ό λ°λμ ν¬ν¨ν΄μΌνλ€.)
κ°μ₯ κΈ΄ κ°μνλ λΆλΆ μμ΄
μμ΄ Aκ° μ£Όμ΄μ‘μ λ, κ°μ₯ κΈ΄ κ°μνλ λΆλΆ μμ΄μ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
μ) μμ΄ A = {10, 30, 10, 20, 20, 10} μΈ κ²½μ°μ κ°μ₯ κΈ΄ κ°μνλ λΆλΆ μμ΄μ A = {10, 30, 10, 20, 20, 10} μ΄κ³ , κΈΈμ΄λ 3μ΄λ€.
D[i]= A[1]~A[n]κΉμ§ μμ΄μ΄ μμ λ, A[i]λ₯Ό λ§μ§λ§μΌλ‘ νλ κ°μ₯ κΈ΄ κ°μνλ λΆλΆ μμ΄μ κΈΈμ΄(A[i]λ₯Ό λ°λμ ν¬ν¨ν΄μΌνλ€.)
κ°μ₯ κΈ΄ λ°μ΄ν λ λΆλΆ μμ΄
μμ΄ Sκ° μ΄λ€ μ Skλ₯Ό κΈ°μ€μΌλ‘ S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SNμ λ§μ‘±νλ€λ©΄, κ·Έ μμ΄μ λ°μ΄ν λ μμ΄μ΄λΌκ³ νλ€.
μ) {10, 20, 30, 25, 20}κ³Ό {10, 20, 30, 40}, {50, 40, 25, 10} μ λ°μ΄ν λ μμ΄μ΄μ§λ§, {1, 2, 3, 2, 1, 2, 3, 2, 1}κ³Ό {10, 20, 30, 40, 20, 30} μ λ°μ΄ν λ μμ΄μ΄ μλλ€.
κ°μ₯ κΈ΄ μ¦κ°νλ λΆλΆ μμ΄(D1)κ³Ό κ°μ₯ κΈ΄ κ°μνλ λΆλΆ μμ΄(D2)λ₯Ό ꡬνλ€μ D1+D2-1μ ꡬνλ©΄λλ€.
μ°μν©
nκ°μ μ μλ‘ μ΄λ£¨μ΄μ§ μμμ μμ΄μ΄ μ£Όμ΄μ§λ€. μ°λ¦¬λ μ΄ μ€ μ°μλ λͺ κ°μ μ«μλ₯Ό μ νν΄μ ꡬν μ μλ ν© μ€ κ°μ₯ ν° ν©μ ꡬνλ €κ³ νλ€. λ¨, μ«μλ ν κ° μ΄μ μ νν΄μΌ νλ€.
μ) 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 μ΄λΌλ μμ΄μ΄ μ£Όμ΄μ‘λ€κ³ νμ. μ¬κΈ°μ μ λ΅μ 12+21μΈ 33μ΄ μ λ΅μ΄ λλ€.
D[i]=A[i]λ‘ λλλ μ΅λ μ°μν©
A[i-1]λ‘ λλλ μ°μν©μ ν¬ν¨ D[i-1]+A[i]
μλ‘μ΄ μ°μν© μμ A[i]
κ³λ¨ μ€λ₯΄κΈ°
κ³λ¨ μ€λ₯΄κΈ° κ²μμ κ³λ¨ μλ μμμ λΆν° κ³λ¨ κΌλκΈ°μ μμΉν λμ°©μ κΉμ§ κ°λ κ²μμ΄λ€. κ°κ°μ κ³λ¨μλ μΌμ ν μ μκ° μ°μ¬ μλλ° κ³λ¨μ λ°μΌλ©΄ κ·Έ κ³λ¨μ μ°μ¬ μλ μ μλ₯Ό μ»κ² λλ€.
κ³λ¨μ ν λ²μ ν κ³λ¨μ© λλ λ κ³λ¨μ© μ€λ₯Ό μ μλ€. μ¦, ν κ³λ¨μ λ°μΌλ©΄μ μ΄μ΄μ λ€μ κ³λ¨μ΄λ, λ€μ λ€μ κ³λ¨μΌλ‘ μ€λ₯Ό μ μλ€.
μ°μλ μΈ κ°μ κ³λ¨μ λͺ¨λ λ°μμλ μλλ€. λ¨, μμμ μ κ³λ¨μ ν¬ν¨λμ§ μλλ€.
λ§μ§λ§ λμ°© κ³λ¨μ λ°λμ λ°μμΌ νλ€.
λ°λΌμ 첫 λ²μ§Έ κ³λ¨μ λ°κ³ μ΄μ΄ λ λ²μ§Έ κ³λ¨μ΄λ, μΈ λ²μ§Έ κ³λ¨μΌλ‘ μ€λ₯Ό μ μλ€. νμ§λ§, 첫 λ²μ§Έ κ³λ¨μ λ°κ³ μ΄μ΄ λ€ λ²μ§Έ κ³λ¨μΌλ‘ μ¬λΌκ°κ±°λ, 첫 λ²μ§Έ, λ λ²μ§Έ, μΈλ²μ§Έ κ³λ¨μ μ°μν΄μ λͺ¨λ λ°μ μλ μλ€.
D[i][j]=iλ²μ§Έ κ³λ¨μ μ¬λμ λ μ΄ μ μμ μ΅λκ°. (iλ²μ§Έ κ³λ¨μ jκ° μ°μν΄μ μ€λ₯Έ κ³λ¨)
D[i][0]=0κ°μ°μ(iλ²μ§Έ κ³λ¨μ μ¬λΌκ°μΌ νκΈ° λλ¬Έμ λΆκ°λ₯ν κ²½μ°)
D[i][1]=1κ°μ°μ(i-1μ λ°μΌλ©΄ μλλ€.)=max(D[i-2][1],D[i-2][2])+a[i]
D[i][2]=2κ°μ°μ(iλ²μ§Έ κ³λ¨μ λ°μμΌνκ³ , λ°λμ 1κ° μ°μν΄μ μ¬λΌμ¨ κ³λ¨μ΄μ΄μΌνλ€.)=D[i-1][1]+a[i]
μ΄λ κ²½μ°μ μλ‘ λ°μΌλ‘ λΉΌμ€λ€λ©΄ 2μ°¨μμμ 1μ°¨μμΌλ‘ μ°¨μμ μ€μΌ μ μλ€.
D[i]=iλ²μ§Έ κ³λ¨μ μ¬λΌκ°μ λ, μ΅λ μ μ
1κ° μ°μ : i-1λ²μ§Έ κ³λ¨μ λ°μΌλ©΄ μλ¨
i-2λ λ°λμ λ°μμ΄μΌ ν¨
D[i-2]+A[i]
2κ° μ°μ : i-1λ²μ§Έ κ³λ¨μ λ°κ³ , i-2λ λ°μΌλ©΄ μλ¨
i-3λ²μ§Έ κ³λ¨μ λ°λμ λ°μμΌ ν¨
D[i-3]+A[i-1]+A[i]
μ κ³±μμ ν©
μ΄λ€ μμ°μ Nμ κ·Έλ³΄λ€ μμ μ κ³±μλ€μ ν©μΌλ‘ λνλΌ μ μλ€. μλ₯Ό λ€μ΄ 11=3^2+1^2+1^2(3κ° ν)μ΄λ€. μ΄λ° ννλ°©λ²μ μ¬λ¬ κ°μ§κ° λ μ μλλ°, 11μ κ²½μ° 11=2^2+2^2+1^2+1^2+1^2(5κ° ν)λ κ°λ₯νλ€. μ΄ κ²½μ°, μνμ μν¬λΌν μ€λ β11μ 3κ° νμ μ κ³±μ ν©μΌλ‘ ννν μ μλ€.βλΌκ³ λ§νλ€. λν 11μ κ·Έλ³΄λ€ μ μ νμ μ κ³±μ ν©μΌλ‘ ννν μ μμΌλ―λ‘, 11μ κ·Έ ν©μΌλ‘μ¨ ννν μ μλ μ κ³±μ νμ μ΅μ κ°μλ 3μ΄λ€.
D[i]=μμ°μ Nμ μ΄λ κ² μ κ³±μλ€μ ν©μΌλ‘ ννν λμ κ·Έ νμ μ΅μκ°μ
λ§μ§λ§νμ΄ μ€μνλ€.
min(D[i-j^2]+1) (1<=i<=j^2)
νμΌ μ±μ°κΈ°
3ΓN ν¬κΈ°μ λ²½μ 2Γ1, 1Γ2 ν¬κΈ°μ νμΌλ‘ μ±μ°λ κ²½μ°μ μλ₯Ό ꡬν΄λ³΄μ.
D[i]=3Xiλ₯Ό μ±μ°λ λ°©λ²μ μ
D[i]=3*D[i-2]+2*D[i-4]+2*D[i-6]+...
νλλ° μμ΄
κ·Έλ¦Όκ³Ό κ°μ΄ μΌκ°νμ΄ λμ λͺ¨μμΌλ‘ λμ¬μ Έ μλ€. 첫 μΌκ°νμ μ μΌκ°νμΌλ‘ λ³μ κΈΈμ΄λ 1μ΄λ€. κ·Έ λ€μμλ λ€μκ³Ό κ°μ κ³Όμ μΌλ‘ μ μΌκ°νμ κ³μ μΆκ°νλ€. λμ μμ κ°μ₯ κΈ΄ λ³μ κΈΈμ΄λ₯Ό kλΌ νμ λ, κ·Έ λ³μ κΈΈμ΄κ° kμΈ μ μΌκ°νμ μΆκ°νλ€.
νλλ° μμ΄ P(N)μ λμ μ μλ μ μΌκ°νμ λ³μ κΈΈμ΄μ΄λ€. P(1)λΆν° P(10)κΉμ§ 첫 10κ° μ«μλ 1, 1, 1, 2, 2, 3, 4, 5, 7, 9μ΄λ€.
Nμ΄ μ£Όμ΄μ‘μ λ, P(N)μ ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
D[i]=P(i)νλλ° μμ΄
D[i-2]+D[i-3]
D[i-5]+D[i-1]
ν©λΆν΄
0λΆν° NκΉμ§μ μ μ Kκ°λ₯Ό λν΄μ κ·Έ ν©μ΄ Nμ΄ λλ κ²½μ°μ μλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
λ§μ μ μμκ° λ°λ κ²½μ°λ λ€λ₯Έ κ²½μ°λ‘ μΌλ€(1+2μ 2+1μ μλ‘ λ€λ₯Έ κ²½μ°). λν ν κ°μ μλ₯Ό μ¬λ¬ λ² μΈ μλ μλ€.
D[K][N]=μ μ 0λΆν° NκΉμ§μ μ μ Kκ°λ₯Ό λν΄μ Nμ΄ λ§λ€μ΄μ§λ κ²½μ°μ μ
+=D[K-1][N-L] (0<=L<=N)
μνΈ μ½λ
μκ·Ό: κ·Έλ₯ κ°λ¨ν μνΈν νμ. Aλ₯Ό 1μ΄λΌκ³ νκ³ , Bλ 2λ‘, κ·Έλ¦¬κ³ Zλ 26μΌλ‘ νλκ±°μΌ. μ μ: κ·ΈλΌ μλΌ. λ§μ½, "BEAN"μ μνΈννλ©΄ 25114κ° λμ€λλ°, μ΄κ±Έ λ€μ κΈμλ‘ λ°κΎΈλ λ°©λ²μ μ¬λ¬κ°μ§κ° μμ΄. μκ·Ό: κ·Έλ λ€. 25114λ₯Ό λ€μ μμ΄λ‘ λ°κΎΈλ©΄, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" μ΄ 6κ°μ§κ° λμ€λλ°, BEANμ΄ λ§λ λ¨μ΄λΌλ건 μ½κ² μμ μμμ? μ μ: μκ° μ μ νμ§ μμλ€ γ γ λ§μ½ λ΄κ° 500μ리 κΈμλ₯Ό μνΈν νλ€κ³ ν΄λ΄. κ·Έ λλ λμ¬ μ μλ ν΄μμ΄ μ λ§ λ§μλ°, κ·Έκ±Έ μΈμ λ€ν΄λ΄? μκ·Ό: μΌλ§λ λ§μλ°? μ μ: ꡬν΄λ³΄μ! μ΄λ€ μνΈκ° μ£Όμ΄μ‘μ λ, κ·Έ μνΈμ ν΄μμ΄ λͺ κ°μ§κ° λμ¬ μ μλμ§ κ΅¬νλ νλ‘κ·Έλ¨μ μμ±νμμ€.
D[i]=iλ²μ§Έ λ¬ΈμκΉμ§ ν΄μνμ λ, λμ¬ μ μλ ν΄μμ κ°μ§ μ
1μ리 μνΈ(0μ μΈ)
2μ리 μνΈ(10~26)
Last updated
Was this helpful?