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 ν μΉΈμ μ±μ°λ 볡μ‘λ(ν¨μνλμ μκ° λ³΅μ‘λ)μ΄λ€.
// cpp
int memo[100]; //memoization
int fibonacci(int n){
if(n<=1){
return n;
}else{
if(memo[n]>0){
return memo[n];
}
memo[n] = fibonacci(n-1)+fibonacci(n-2);
return memo[n];
}
}
# python
# memorization
d = [0] * 100
def fibonacci_recursion(x):
# 1 or 2 λ 1
if x == 1 or x == 2:
return 1
# μ΄λ―Έ νλ² νΈμΆλ μ μλ κ°μ κΈ°μ΅ν΄λ κ° λ°ν
if d[x]!=0:
return d[x]
# νλ²λ νΈμΆλμ μλ κ°μ μΆκ°
d[x] = fibonacci_recursion(x-1) + fibonacci_recursion(x-2)
return d[x]
print(fibonacci_recursion(6))
Bottom-up
λ¬Έμ λ₯Ό ν¬κΈ°κ° μμ λ¬Έμ λΆν° μ°¨λ‘λλ‘ νΌλ€.
λ¬Έμ μ ν¬κΈ°λ₯Ό μ‘°κΈμ© ν¬κ² λ§λ€λ©΄μ λ¬Έμ λ₯Ό νΌλ€.
μμ λ¬Έμ λ₯Ό νλ©΄μ μκΈ° λλ¬Έμ, ν° λ¬Έμ λ νμ ν μ μλ€.
int d[100];
int fibonacci(int n){
d[0]=1;
d[1]=1;
for(int i=2;i<=n;i++){
d[i]=d[i-1]+d[i-2];
}
return d[n];
}
# bottom-up
# dp table
d = [0] * 100
def fibonacci_loop(n):
d[1] = 1
d[2] = 1
for i in range(3,n+1):
d[i] = d[i-1]+d[i-2]
print(d[n])
fibonacci_loop(99)
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
#include <iostream>
//Top-Down(μ¬κ·)
int d[1000001];
int divn(int n){
if(n==1) return 0;
if(d[n]>0) return d[n];
//-1
d[n]=divn(n-1)+1;
if(n%2==0){
int temp=divn(n/2)+1;
if(d[n]>temp) d[n] = temp;
}
if(n%3==0){
int temp=divn(n/3)+1;
if(d[n]>temp) d[n] = temp;
}
return d[n];
}
bottom-up
//Bottom-up
void divbu(int n){
d[1]=0;
for(int i=2;i<=n;i++){
d[i]=d[i-1]+1;
if(i%2==0 && d[i]>d[i/2]+1){
d[i]=d[i/2]+1;
}
if(i%3==0 && d[i]>d[i/3]+1){
d[i]=d[i/3]+1;
}
}
printf("%d",d[n]);
}
2Xn νμΌλ§
2Xn μ§μ¬κ°νμ 1x2,2x1νμΌλ‘ μ±μ°λ λ°©λ²μ μ => D[n]=2xiμ§μ¬κ°νμ μ±μ°λ λ°©λ²μ μ => D[n]=D[n-1]+D[n-2]
μ΄ λ, n=0μΌ λλ κ²½μ°μ μμ΄κΈ° λλ¬Έμ 1μ μΆλ ₯νλ€.
bottom-up
#include <iostream>
using namespace std;
int d[10001];
int main() {
int x;
cin >> x;
d[1]=1;
d[0]=1;
for(int i=2;i<=x;i++){
d[i]=d[i-1]+d[i-2];
d[i]%=10007;
}
cout << d[x] << "\n";
}
2xn νμΌλ§ 2
2Xn μ§μ¬κ°νμ 1x2,2x1,2x2νμΌλ‘ μ±μ°λ λ°©λ²μ μ => D[n]=2xiμ§μ¬κ°νμ μ±μ°λ λ°©λ²μ μ => D[n]=D[n-1]+2*D[n-2]
bottom-up
#include <iostream>
using namespace std;
int d[10001];
int main() {
int x;
cin >> x;
d[1]=1;
d[0]=1;
for(int i=2;i<=x;i++){
d[i]=d[i-1]+2*d[i-2];
d[i]%=10007;
}
cout << d[x] << "\n";
}
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
#include <iostream>
using namespace std;
int d[10001];
int main() {
int t;
cin >> t;
while(t--){
int x;
cin >> x;
d[1]=1;
d[0]=1;
d[2]=2;
for(int i=2;i<=x;i++){
d[i]=d[i-1]+d[i-2]+d[i-3];
}
cout << d[x] << "\n";
}
}
λΆμ΄λΉ΅ νλ§€νκΈ°
λΆμ΄λΉ΅ 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)
#include <iostream>
using namespace std;
int d[10001];//λΆμ΄λΉ΅ nκ°λ₯Ό νμμ μ»μ μ μλ μ΅λμμ΅
int p[10001];
int main(){
int n;//λΆμ΄λΉ΅μ μ
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&p[i]);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
d[i]=max(d[i],d[i-j]+p[j]);
}
}
cout<<d[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]
#include <iostream>
using namespace std;
int d[101][9];
int main(){
int n,ans=0;
scanf("%d",&n);
for(int j=1;j<=9;j++){
d[1][j]=1;
}
for(int i=2;i<=n;i++){
for(int j=0;j<=9;j++){
d[i][j]=0;
if(j-1>=0)d[i][j]+=d[i-1][j-1];
if(j+1<=9)d[i][j]+=d[i-1][j+1];
}
}
for(int j=0;j<=9;j++){
ans+=d[n][j];
}
printf("%d",ans);
}
μ€λ₯΄λ§ μ
μ€λ₯΄λ§ μλ μμ μλ¦¬κ° μ€λ¦μ°¨μμ μ΄λ£¨λ μλ₯Ό λ§νλ€. μ΄ λ, μΈμ ν μκ° κ°μλ μ€λ¦μ°¨μμΌλ‘ μΉλ€. μλ₯Ό λ€μ΄, 2234μ 3678, 11119λ μ€λ₯΄λ§ μμ΄μ§λ§, 2232, 3676, 91111μ μ€λ₯΄λ§ μκ° μλλ€. μμ κΈΈμ΄ Nμ΄ μ£Όμ΄μ‘μ λ, μ€λ₯΄λ§ μμ κ°μλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€. μλ 0μΌλ‘ μμν μ μλ€.
=> D[N][L]=Nμ리 μ€λ₯΄λ§μ, λ§μ§λ§μ L => D[N][L]=sum(D[N-1][k])(0<=k<=L)
#include <iostream>
using namespace std;
int d[1001][10];
int main(){
int n;
scanf("%d",&n);
for(int j=0;j<=9;j++){
d[1][j]=1;
}
for(int i=2;i<=n;i++)
for(int j=0;j<=9;j++)
for(int k=0;k<=j;k++)
d[i][j]+=d[i-1][k];
int ans=0;
for(int j=0;j<=9;j++){
ans+=d[n][j];
}
printf("%d",ans);
}
μ΄μΉμ
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)
#include <iostream>
using namespace std;
int d[91];
int main(){
int n;
scanf("%d",&n);
d[1]=1;
d[2]=1;
for(int i=3;i<=n;i++){
d[i]=d[i-1]+d[i-2];
}
printf("%d",d[n]);
}
μ€ν°μ»€
μ€ν°μ»€ 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])
#include <iostream>
using namespace std;
int d[100000][3];
int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
int array[n][2];
for(int i=0;i<2;i++){
for(int j=0;j<n;j++){
scanf("%d",&array[j][i]);
}
}
d[0][0]=0;
d[0][1]=array[0][0];
d[0][2]=array[0][1];
for(int i=1;i<n;i++){
d[i][0]=max(max(d[i-1][0], d[i-1][1]),d[i-1][2]);
d[i][1]=max(d[i-1][0],d[i-1][2])+array[i][0];
d[i][2]=max(d[i-1][0],d[i-1][1])+array[i][1];
}
printf("%d\n",max(max(d[n-1][0],d[n-1][1]),d[n-1][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]
#include <iostream>
using namespace std;
int d[10001][3];
int main(){
int n;
scanf("%d",&n);
int g[n];
for(int i=1;i<=n;i++){
scanf("%d",&g[i]);
}
d[0][0]=d[0][1]=d[0][2]=0;
for(int i=1;i<=n;i++){
d[i][0]= max(max(d[i-1][0],d[i-1][1]),d[i-1][2]);
d[i][1]= d[i-1][0]+g[i];
d[i][2]= d[i-1][1]+g[i];
}
printf("%d",max(max(d[n][0],d[n][1]),d[n][2]));
}
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])
d[0]=0;
d[1]=g[1];
d[2]=g[1]+g[2];
for(int i=3;i<=n;i++){
d[i]= max(max(d[i-1],d[i-2]+g[i]),d[i-3]+g[i]+g[i-1]);
}
κ°μ₯ κΈ΄ μ¦κ°νλ λΆλΆ μμ΄
μμ΄ 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]λ₯Ό λ°λμ ν¬ν¨ν΄μΌνλ€.)
#include <iostream>
using namespace std;
int d[1001];
int main(){
int n; //μμ΄μ ν¬κΈ°
scanf("%d",&n);
int a[n];
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++){
d[i]=1;
for(int j=0;j<i;j++){
if(a[i]>a[j]&&d[i]<d[j]+1)d[i]=d[j]+1;
}
}
int maxd=0;
for(int i=0;i<n;i++){
if(maxd<d[i])maxd=d[i];
}
printf("%d",maxd);
}
κ°μ₯ κΈ΄ κ°μνλ λΆλΆ μμ΄
μμ΄ 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]λ₯Ό λ°λμ ν¬ν¨ν΄μΌνλ€.)
#include <iostream>
using namespace std;
int d[1001];
int main(){
int n; //μμ΄μ ν¬κΈ°
scanf("%d",&n);
int a[n];
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++){
d[i]=1;
for(int j=0;j<i;j++){
if(a[i]<a[j]&&d[i]<d[j]+1)d[i]=d[j]+1;
}
}
int maxd=0;
for(int i=0;i<n;i++){
if(maxd<d[i])maxd=d[i];
}
printf("%d",maxd);
}
κ°μ₯ κΈ΄ λ°μ΄ν λ λΆλΆ μμ΄
μμ΄ 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μ ꡬνλ©΄λλ€.
#include <stdio.h>
/*
μμ΄ 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} μ λ°μ΄ν λ μμ΄μ΄ μλλ€.
μμ΄ Aκ° μ£Όμ΄μ‘μ λ, κ·Έ μμ΄μ λΆλΆ μμ΄ μ€ λ°μ΄ν λ μμ΄μ΄λ©΄μ κ°μ₯ κΈ΄ μμ΄μ κΈΈμ΄λ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
첫째 μ€μ μμ΄ Aμ ν¬κΈ° Nμ΄ μ£Όμ΄μ§κ³ , λμ§Έ μ€μλ μμ΄ Aλ₯Ό μ΄λ£¨κ³ μλ Aiκ° μ£Όμ΄μ§λ€. (1 β€ N β€ 1,000, 1 β€ Ai β€ 1,000)
*/
int d[1001];
int d2[1001];
int main() {
int n;
scanf("%d",&n);
int a[n+1];
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++){
d[i]=1;
for(int j=0;j<=i;j++){
if(a[i]>a[j]&&d[i]<d[j]+1){
d[i]=d[j]+1;
}
}
}
for (int i=n-1; i>=0; i--) {
d2[i] = 1;
for (int j=i+1; j<n; j++) {
if (a[i] > a[j] && d2[j]+1 > d2[i]) {
d2[i] = d2[j]+1;
}
}
}
int ans =0 ;
for(int i=0;i<n;i++){
if(ans<d[i]+d2[i]-1){
ans=d[i]+d2[i]-1;
}
}
printf("%d",ans);
return 0;
}
μ°μν©
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]
#include <iostream>
using namespace std;
int d[100001]; //A[i]λ‘ λλλ μ΅λ μ°μν©
int main(){
int n; //μ°μλ μ«μμ μ
scanf("%d",&n);
int a[n];
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
d[0]=a[0];
for(int i=1;i<n;i++){
d[i]=max(d[i-1]+a[i],a[i]);
}
int ans=d[0];
for(int i=1;i<n;i++){
if(ans<d[i])ans=d[i];
}
printf("%d",ans);
}
κ³λ¨ μ€λ₯΄κΈ°
κ³λ¨ μ€λ₯΄κΈ° κ²μμ κ³λ¨ μλ μμμ λΆν° κ³λ¨ κΌλκΈ°μ μμΉν λμ°©μ κΉμ§ κ°λ κ²μμ΄λ€. κ°κ°μ κ³λ¨μλ μΌμ ν μ μκ° μ°μ¬ μλλ° κ³λ¨μ λ°μΌλ©΄ κ·Έ κ³λ¨μ μ°μ¬ μλ μ μλ₯Ό μ»κ² λλ€.
κ³λ¨μ ν λ²μ ν κ³λ¨μ© λλ λ κ³λ¨μ© μ€λ₯Ό μ μλ€. μ¦, ν κ³λ¨μ λ°μΌλ©΄μ μ΄μ΄μ λ€μ κ³λ¨μ΄λ, λ€μ λ€μ κ³λ¨μΌλ‘ μ€λ₯Ό μ μλ€.
μ°μλ μΈ κ°μ κ³λ¨μ λͺ¨λ λ°μμλ μλλ€. λ¨, μμμ μ κ³λ¨μ ν¬ν¨λμ§ μλλ€.
λ§μ§λ§ λμ°© κ³λ¨μ λ°λμ λ°μμΌ νλ€.
λ°λΌμ 첫 λ²μ§Έ κ³λ¨μ λ°κ³ μ΄μ΄ λ λ²μ§Έ κ³λ¨μ΄λ, μΈ λ²μ§Έ κ³λ¨μΌλ‘ μ€λ₯Ό μ μλ€. νμ§λ§, 첫 λ²μ§Έ κ³λ¨μ λ°κ³ μ΄μ΄ λ€ λ²μ§Έ κ³λ¨μΌλ‘ μ¬λΌκ°κ±°λ, 첫 λ²μ§Έ, λ λ²μ§Έ, μΈλ²μ§Έ κ³λ¨μ μ°μν΄μ λͺ¨λ λ°μ μλ μλ€.
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]
#include <iostream>
using namespace std;
int d[301][3]; //A[i]λ‘ λλλ μ΅λ μ μ
int main(){
int n; //κ³λ¨μ
scanf("%d",&n);
int a[n];//κ° κ³λ¨ μ μ
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
d[0][1]=a[0];
d[1][1]=a[1];
d[1][2]=a[1]+a[0];
for(int i=2;i<n;i++){
d[i][1]=max(d[i-2][1],d[i-2][2])+a[i];
d[i][2]=d[i-1][1]+a[i];
}
printf("%d",max(d[n-1][1],d[n-1][2]));
}
μ΄λ κ²½μ°μ μλ‘ λ°μΌλ‘ λΉΌμ€λ€λ©΄ 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]
#include <iostream>
using namespace std;
int d[301]; //A[i]λ‘ λλλ μ΅λ μ μ
int a[301];//κ° κ³λ¨ μ μ
int main(){
int n; //κ³λ¨μ
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
d[1]=a[1];
d[2]=a[1]+a[2];
for(int i=3;i<=n;i++){
d[i]=max(d[i-2]+a[i],d[i-3]+a[i-1]+a[i]);
}
printf("%d",d[n]);
}
μ κ³±μμ ν©
μ΄λ€ μμ°μ 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)
#include <iostream>
using namespace std;
int d[100001]; //μ κ³±ν©μΌλ‘ νννλ μ΅μν κ°μ
int main(){
int n; //μμ°μ
scanf("%d",&n);
for(int i=1;i<=n;i++){
d[i]=i; //1^2μΌλ‘ ννν κ°μ(μ¦, μ΅λν)
for(int j=1;j*j<=i;j++){
if(d[i]>d[i-j*j]+1)d[i]=d[i-j*j]+1;
}
}
printf("%d",d[n]);
}
νμΌ μ±μ°κΈ°
3ΓN ν¬κΈ°μ λ²½μ 2Γ1, 1Γ2 ν¬κΈ°μ νμΌλ‘ μ±μ°λ κ²½μ°μ μλ₯Ό ꡬν΄λ³΄μ.
D[i]=3Xiλ₯Ό μ±μ°λ λ°©λ²μ μ
D[i]=3*D[i-2]+2*D[i-4]+2*D[i-6]+...
#include <iostream>
using namespace std;
int d[31]; //3*iλ₯Ό ννν μ μλ κ²½μ°μ μ
int main(){
int n;
scanf("%d",&n);
d[0]=1;
for (int i=2; i<=n; i+=2) {
d[i] = d[i-2]*3;
for (int j=i-4; j>=0; j-=2) {
d[i] += d[j]*2;
}
}
printf("%d",d[n]);
}
νλλ° μμ΄

κ·Έλ¦Όκ³Ό κ°μ΄ μΌκ°νμ΄ λμ λͺ¨μμΌλ‘ λμ¬μ Έ μλ€. 첫 μΌκ°νμ μ μΌκ°νμΌλ‘ λ³μ κΈΈμ΄λ 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]
#include <iostream>
using namespace std;
int d[101]; //νλλ°μμ΄
int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
d[0]=0;
d[1]=d[2]=1;
for (int i=3; i<=n; i++) {
d[i] = d[i-2]+d[i-3];
}
printf("%d\n",d[n]);
}
}
ν©λΆν΄
0λΆν° NκΉμ§μ μ μ Kκ°λ₯Ό λν΄μ κ·Έ ν©μ΄ Nμ΄ λλ κ²½μ°μ μλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
λ§μ μ μμκ° λ°λ κ²½μ°λ λ€λ₯Έ κ²½μ°λ‘ μΌλ€(1+2μ 2+1μ μλ‘ λ€λ₯Έ κ²½μ°). λν ν κ°μ μλ₯Ό μ¬λ¬ λ² μΈ μλ μλ€.
D[K][N]=μ μ 0λΆν° NκΉμ§μ μ μ Kκ°λ₯Ό λν΄μ Nμ΄ λ§λ€μ΄μ§λ κ²½μ°μ μ
+=D[K-1][N-L] (0<=L<=N)
#include <iostream>
using namespace std;
long long int d[201][201]; //ν©λΆν΄
int main(){
int n,k;
scanf("%d %d",&k,&n);
d[0][0]=1LL;
for(int i=1;i<=k;i++){
for(int j=0;j<=n;j++){
for(int l=0;l<=j;l++){
d[i][j]+=d[i-1][j-l];
d[i][j]%=1000000000;
}
}
}
printf("%lld",d[k][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?