프로그래밍

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

[난이도] Silver5
[유형] DP

[풀이]
set a[3] 과 같이 선언하여
a[1]에는 1개의 제곱수로 만들 수 있는 숫자들,
a[2]에는 2개의 제곱수를 만들 수 있는 숫자들을 저장합니다.
set을 사용한 이유는 1^2+2^2, 2^2+1^2 등 중복되는 경우가 저장될 수 있기 때문입니다.
a[2]는 a[1]의 원소들로 2중 for문으로 구할 수 있으며
중간에 n과 동일한 수가 나오면 제곱수의 개수를 return 해줍니다.

a[1],a[2]를 구해놨으면 3개와 4개의 제곱수로 만들어진 n도 한번에 구할 수 있습니다.

3개로 만들 수 있는 제곱수는 모든 a[1]을 순회하면서 현재 나온 수가 v일때,
a[2]에 n-v가 있다면 제곱수 3개로 n을 만들 수 있다는 의미이므로 3을 return 해줍니다.

4일때도 마찬가지로
a[2]를 순회하면서 현재 나온 수가 v일때 a[2]에 n-v가 있다면 제곱수 4개로 n을 만들 수 있다는 의미이므로
4를 return 해주면 됩니다.

#include <cstdio>
#include <cmath>
#include <set>
using namespace std;
int n;
set<int> a[3];
int sol(){
    for(int i=1;i<=sqrt(n);i++){
        if(i*i==n) return 1;
        a[1].insert(i*i);
    }
    for(auto v1 : a[1]){
        for(auto v2 : a[1]){
            if(v1+v2==n) return 2;
            a[2].insert(v1+v2);
        }
    }    
    for(int i=1;i<3;i++){
        for(auto v : a[i]){
            if(a[2].find(n-v) != a[2].end()) return i+2;
        }
    }
    return 0;
}
int main(){
    scanf("%d",&n);
    printf("%d",sol());
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver5/17626.cpp

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

[난이도] Silver2
[유형] DP

[풀이]
재귀만을 이용해서 값을 구하게 되면 w(x,y,z)를 중복으로 실행하는 경우가 여러번 생길 수 있으므로
DP[21][21][21] 배열을 선언하여 메모제이션을 해주어야 한다.
DP[x][y][z]에 값이 있으면 이 값을 return해서 더이상 재귀가 수행되지 않도록 한다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.max
import java.lang.Integer.min
import java.util.*
var dp=Array(21,{Array(21,{Array<Int>(21,{-1})})})
fun sol(n:Int,m:Int,k:Int):Int{
    when {
        (n <= 0 || m <= 0 || k <= 0) -> return 1
        (n > 20 || m > 20 || k > 20) -> return sol(20, 20, 20)
    }
    if(dp[n][m][k]!=-1) return dp[n][m][k]
    dp[n][m][k] = when{
        (n<m&&m<k)->sol(n,m,k-1)+sol(n,m-1,k-1)-sol(n,m-1,k)
        else -> sol(n-1,m,k)+sol(n-1,m-1,k)+sol(n-1,m,k-1)-sol(n-1,m-1,k-1)
    }
    return dp[n][m][k]
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    while(true){
        var (N,M,K) = readLine().split(' ').map{it.toInt()}
        if(N==-1&&M==-1&&K==-1) break
        println("w($N, $M, $K) = ${sol(N,M,K)}")
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/9184.cpp

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

[난이도] Gold5
[유형] DP

[풀이]
DP[n][m] : n번째 원소부터 선택이 가능하고 현재까지 총 m개의 구간을 구했을 때, 만들 수 있는 최댓값

부분합을 미리 구해놓는다 -> sum[i][j] : i~j까지의 합.

Top-Down 방식으로 풀었다. sol(n,m) 은 DP[n][m]

점화식 :
1) n번째 원소를 어느구간에도 포함시키지 않는 경우
=> sol(n,m) = sol(n+1,m) (구간은 증가하지 않고 n만 1 증가)

2) n번째 원소를 첫번째 원소로 해서 만들 수 있는 모든 구간을 구해보는 경우
=> sol(n,m) = max(sum[n][i]+sol(i+2,m+1)) ( n <= i < N )

1,2의 최댓값이 정답이다.

종료조건 :
m==M 인 경우 => 모든 구간을 다 찾았으므로 0을 return
m=N인 경우 => 새로운 구간을 만들 수 없으므로 음의 무한대 -9e8을 return

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,M,a[100],dp[100][51],sum[100][100],inf=9e8;
int sol(int n,int m){
    if(m==M) return 0;
    if(n>=N) return -inf;
    int& ret = dp[n][m];
    if(ret!=-1) return ret;
    ret=sol(n+1,m);
    for(int i=n;i<N;i++){
        ret=max(ret,sum[n][i]+sol(i+2,m+1));
    }
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<N;i++){
        int s = 0;
        for(int j=i;j<N;j++){
            s+=a[j];
            sum[i][j]=s;
        }
    }
    printf("%d",sol(0,0));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2228.cpp

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

[난이도] Gold5
[유형] DP

[풀이]
dp[i] : i원을 만들 수 있는 경우의 수.

#include <cstdio>
#include <cstring>
using namespace std;
int tc,N,M,a[20],dp[10001];
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        memset(dp,0,sizeof(dp));
        for(int i=0;i<N;i++) scanf("%d",&a[i]);
        scanf("%d",&M);
        dp[0]=1;
        for(int i=0;i<N;i++)
            for(int j=1;j<=M;j++)
                if(j-a[i]>=0) dp[j]+=dp[j-a[i]];
        printf("%d\n",dp[M]);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/9084.cpp

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

[난이도] Silver3
[유형] DP

[풀이]
DP[i][j] : 가장 마지막에 더한 숫자가 i이며 j를 만들 수 있는 방법의 수.

위와 같이 마지막에 더한 수 i를 기록할 수 있는 2차원 테이블을 만들어서 풀 수 있다.

import java.io.BufferedReader
import java.io.InputStreamReader
val mod = 1e9.toInt()+9
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var t = readLine().toInt()
    val dp = Array<IntArray>(4) { IntArray(100001) }
    dp[1][1]=1
    dp[2][2]=1
    dp[3][3]=1
    for(i in 1..100000){
        for(j in 1..3){
            if(i-j<0) continue
            for(k in 1..3){
                if(j!=k)
                    dp[j][i]=(dp[j][i]+dp[k][i-j])%mod
            }
        }
    }
    while(t-->0){
        val N = readLine().toInt()
        println(((dp[1][N]+dp[2][N])%mod+dp[3][N])%mod)
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver3/15990.cpp

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

[난이도] Silver1
[유형] DP

[풀이]
DP[i] : 카드 i개를 구매하기 위해 지불해야 하는 최솟값

dp[i] = min(dp[i],dp[i-j]+P[i])

#include <cstdio>
#include <algorithm>
using namespace std;
int N,P[1001],dp[1001];
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&P[i]);
    for(int i=1;i<=N;i++) dp[i]=1e8;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(i-j>=0) dp[i]=min(dp[i],P[j]+dp[i-j]);
        }
    }
    printf("%d",dp[N]);
} 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/16194.cpp

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

[난이도] Silver1
[유형] DP

[풀이]
DP[N][M] : N을 M개의 수를 이용해 만들 수 있는 경우의 수.

주의할점 : tc 마다 계산하면 안되고 n=1000,m=1000 일때를 한번 계산해놓으면 모든 케이스를 구할 수 있으므로 재활용하면 된다.

#include <cstdio>
#include <cstring>
int t,n,m,dp[1001][1001],mod = 1e9+9;
int main(){
    scanf("%d",&t);
    dp[1][1]=dp[2][1]=dp[3][1]=1;
    for(int i=2;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            for(int k=1;k<4;k++){
                if(j-k>0) dp[j][i]+=dp[j-k][i-1];
                dp[j][i]%=mod;
            }
        }
    }
    while(t--){
        scanf("%d%d",&n,&m);
        long long ans = 0;
        for(int i=0;i<=m;i++) ans=(ans+dp[n][i])%mod;
        printf("%lld\n",ans);
    }
} 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/16195.cpp

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

[난이도] Silver1
[유형] DP

[풀이]
DP[N][M] : N을 M개의 수를 이용해 만들 수 있는 경우의 수.

#include <cstdio>
#include <cstring>
int t,n,m,dp[1001][1001],mod = 1e9+9;
int main(){
    scanf("%d",&t);
    dp[1][1]=dp[2][1]=dp[3][1]=1;
    for(int i=2;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            for(int k=1;k<4;k++){
                if(j-k>0) dp[j][i]+=dp[j-k][i-1];
                dp[j][i]%=mod;
            }
        }
    }
    while(t--){
        scanf("%d%d",&n,&m);
        printf("%d\n",dp[n][m]);
    }
} 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/15992.cpp