백준 23816번 옷걸이걸이걸이
https://www.acmicpc.net/problem/23816
23816번: 옷걸이걸이걸이
차례대로 높이가 1, 2, 2, 3인 옷걸이 트리를 놓으면 각각에 옷을 1, 2, 2, 4개 걸 수 있다.
www.acmicpc.net
문제 해석
문제를 자세히 읽어보면 남는 옷걸이를 둘데가 없으므로 모든 옷걸이를 옷장 속으로 넣어야 하고
옷장에 자리 하나당 옷걸이 트리하나를 걸수가 있다.
옷걸이 트리는 높이가 1,2,3,4는 넣을 수 있고
높이가 1인 트리를 넣으면 걸 수있는 옷의 수는 1개,필요한 옷걸이수는 1개
높이가 2인 트리를 넣으면 걸 수있는 옷의 수는 2개,필요한 옷걸이수는 3개
높이가 3인 트리를 넣으면 걸 수있는 옷의 수는 4개,필요한 옷걸이수는 7개
높이가 4인 트리를 넣으면 걸 수있는 옷의 수는 0개,필요한 옷걸이수는 15개 이다.
그렇다면 dp[i][j]의 정의를 옷장의 남은공간이 i개 남은 옷걸이 수가 j개라고 할때의 걸 수있는 옷의 수로 정의를한다면
dp[i][j]=max({dp[i-1][j-15],4+dp[i-1][j-7],2+dp[i-1][j-3],1+dp[i-1][j-1]}) 이다.
i=0, 1<=j 일때 (즉, 옷장에 자리가없고 옷걸이가 남아있을때) dp[i][j]=-1
i=1일때 j=1,3,7,15를 제외한 dp[i][j]=-1 dp[1][1]=1 , dp[1][3]=2 , dp[1][7]=4 ,d p[1][15]=0
초기 설정은 위와 같고 i=2, j=1 부터 위의 점화식을 적용해주면 된다.
코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int dp[5001][10001];
int n,m;
int main(){
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
cin>>n>>m;
for(int i=1; i<10001; i++)
{
dp[0][i]=-1;
dp[1][i]=-1;
}
dp[1][1]=1;
dp[1][3]=2;
dp[1][7]=4;
dp[1][15]=0;
for(int i=2; i<5001; i++)
{
for(int j=1; j<10001; j++)
{
if(1<=j&&j<3)
{
if(dp[i-1][j-1]!=-1)
{
dp[i][j]=1+dp[i-1][j-1];
}
else
{
dp[i][j]=-1;
}
}
else if(3<=j&&j<7)
{
if(dp[i-1][j-3]!=-1&&dp[i-1][j-1]!=-1)
{
dp[i][j]=max(2+dp[i-1][j-3],1+dp[i-1][j-1]);
}
else if(dp[i-1][j-3]==-1&&dp[i-1][j-1]!=-1)
{
dp[i][j]=1+dp[i-1][j-1];
}
else if(dp[i-1][j-3]!=-1&&dp[i-1][j-1]==-1)
{
dp[i][j]=2+dp[i-1][j-3];
}
else if(dp[i-1][j-3]==-1&&dp[i-1][j-1]==-1)
{
dp[i][j]=-1;
}
}
else if(7<=j&&j<15)
{
if(dp[i-1][j-7]!=-1&&dp[i-1][j-3]!=-1&&dp[i-1][j-1]!=-1)
{
dp[i][j]=max({4+dp[i-1][j-7],2+dp[i-1][j-3],1+dp[i-1][j-1]});
}
else if(dp[i-1][j-7]==-1&&dp[i-1][j-3]!=-1&&dp[i-1][j-1]!=-1)
{
dp[i][j]=max(2+dp[i-1][j-3],1+dp[i-1][j-1]);
}
else if(dp[i-1][j-7]!=-1&&dp[i-1][j-3]==-1&&dp[i-1][j-1]!=-1)
{
dp[i][j]=max(4+dp[i-1][j-7],1+dp[i-1][j-1]);
}
else if(dp[i-1][j-7]!=-1&&dp[i-1][j-3]!=-1&&dp[i-1][j-1]==-1)
{
dp[i][j]=max(4+dp[i-1][j-7],2+dp[i-1][j-3]);
}
else if(dp[i-1][j-7]==-1&&dp[i-1][j-3]==-1&&dp[i-1][j-1]!=-1)
{
dp[i][j]=dp[i-1][j-1];
}
else if(dp[i-1][j-7]==-1&&dp[i-1][j-3]!=-1&&dp[i-1][j-1]==-1)
{
dp[i][j]=2+dp[i-1][j-3];
}
else if(dp[i-1][j-7]!=-1&&dp[i-1][j-3]==-1&&dp[i-1][j-1]==-1)
{
dp[i][j]=4+dp[i-1][j-7];
}
else if(dp[i-1][j-7]==-1&&dp[i-1][j-3]==-1&&dp[i-1][j-1]==-1)
{
dp[i][j]=-1;
}
}
else if(15<=j)
{
if(dp[i-1][j-15]!=-1&&dp[i-1][j-7]!=-1&&dp[i-1][j-3]!=-1&&dp[i-1][j-1]!=-1)
{
dp[i][j]=max({dp[i-1][j-15],4+dp[i-1][j-7],2+dp[i-1][j-3],1+dp[i-1][j-1]});
}
else if(dp[i-1][j-15]==-1&&dp[i-1][j-7]!=-1&&dp[i-1][j-3]!=-1&&dp[i-1][j-1]!=-1)
{
dp[i][j]=max({4+dp[i-1][j-7],2+dp[i-1][j-3],1+dp[i-1][j-1]});
}
else if(dp[i-1][j-15]!=-1&&dp[i-1][j-7]==-1&&dp[i-1][j-3]!=-1&&dp[i-1][j-1]!=-1)
{
dp[i][j]=max({dp[i-1][j-15],2+dp[i-1][j-3],1+dp[i-1][j-1]});
}
else if(dp[i-1][j-15]!=-1&&dp[i-1][j-7]!=-1&&dp[i-1][j-3]==-1&&dp[i-1][j-1]!=-1)
{
dp[i][j]=max({dp[i-1][j-15],4+dp[i-1][j-7],1+dp[i-1][j-1]});
}
else if(dp[i-1][j-15]!=-1&&dp[i-1][j-7]!=-1&&dp[i-1][j-3]!=-1&&dp[i-1][j-1]==-1)
{
dp[i][j]=max({dp[i-1][j-15],4+dp[i-1][j-7],2+dp[i-1][j-3]});
}
else if(dp[i-1][j-15]==-1&&dp[i-1][j-7]==-1&&dp[i-1][j-3]!=-1&&dp[i-1][j-1]!=-1)
{
dp[i][j]=max(2+dp[i-1][j-3],1+dp[i-1][j-1]);
}
else if(dp[i-1][j-15]==-1&&dp[i-1][j-7]!=-1&&dp[i-1][j-3]==-1&&dp[i-1][j-1]!=-1)
{
dp[i][j]=max(4+dp[i-1][j-7],1+dp[i-1][j-1]);
}
else if(dp[i-1][j-15]==-1&&dp[i-1][j-7]!=-1&&dp[i-1][j-3]!=-1&&dp[i-1][j-1]==-1)
{
dp[i][j]=max(4+dp[i-1][j-7],2+dp[i-1][j-3]);
}
else if(dp[i-1][j-15]!=-1&&dp[i-1][j-7]==-1&&dp[i-1][j-3]==-1&&dp[i-1][j-1]!=-1)
{
dp[i][j]=max(dp[i-1][j-15],1+dp[i-1][j-1]);
}
else if(dp[i-1][j-15]!=-1&&dp[i-1][j-7]==-1&&dp[i-1][j-3]!=-1&&dp[i-1][j-1]==-1)
{
dp[i][j]=max(dp[i-1][j-15],2+dp[i-1][j-3]);
}
else if(dp[i-1][j-15]!=-1&&dp[i-1][j-7]!=-1&&dp[i-1][j-3]==-1&&dp[i-1][j-1]==-1)
{
dp[i][j]=max(dp[i-1][j-15],4+dp[i-1][j-7]);
}
else if(dp[i-1][j-15]==-1&&dp[i-1][j-7]==-1&&dp[i-1][j-3]==-1&&dp[i-1][j-1]!=-1)
{
dp[i][j]=1+dp[i-1][j-1];
}
else if(dp[i-1][j-15]==-1&&dp[i-1][j-7]==-1&&dp[i-1][j-3]!=-1&&dp[i-1][j-1]==-1)
{
dp[i][j]=2+dp[i-1][j-3];
}
else if(dp[i-1][j-15]==-1&&dp[i-1][j-7]!=-1&&dp[i-1][j-3]==-1&&dp[i-1][j-1]==-1)
{
dp[i][j]=4+dp[i-1][j-7];
}
else if(dp[i-1][j-15]!=-1&&dp[i-1][j-7]==-1&&dp[i-1][j-3]==-1&&dp[i-1][j-1]==-1)
{
dp[i][j]=dp[i-1][j-15];
}
else if(dp[i-1][j-15]==-1&&dp[i-1][j-7]==-1&&dp[i-1][j-3]==-1&&dp[i-1][j-1]==-1)
{
dp[i][j]=-1;
}
}
}
}
cout<<dp[n][m]<<"\n";
}여기서 중요한게 있는데 dp[i][j]=max({dp[i-1][j-15],4+dp[i-1][j-7],2+dp[i-1][j-3],1+dp[i-1][j-1]})를 생각없이 넣어버리면 안된다.
만약 max속에 4개 인자 dp[i-1][j-15] , dp[i-1][j-7] , dp[i-1][j-3] , dp[i-1][j-1] 중
값이 -1인것이 있으면 그건 후보에서 제외한 후에 max를 사용해야한다.
만약 4개 전부 -1이면 dp[i][j]는 -1의 값을 가져야한다.
이 부분 처리를 간결하게 어떻게 해야할지 모르겠어서 j범위에 따라 각각 2,4,8,16가지 경우를 모두써서 제출해서 맞긴했는데 눈이 너무 아팠다....
'백준문제풀이' 카테고리의 다른 글
| 백준 11053번 가장 긴 증가하는 부분 수열 문제풀이 c++ (0) | 2022.01.29 |
|---|---|
| 백준 2225번 합분해 문제풀이 c++ (0) | 2022.01.26 |
| 백준 1111번 IQ Test 문제풀이 c++ (0) | 2022.01.25 |
| 백준 문제 23327번 리그전 오브 레전드 문제풀이 c++ (0) | 2022.01.20 |
| 백준 문제 17070번 파이프 옮기기 1 문제풀이 c++ (0) | 2022.01.19 |