[BOJ 33040, 33041 (조금 어려움)] 마작 거신병 (C++)
개인적인 난이도 :
아이디어 - 조금 어려움
구현 - 쉬움
재미 - 재밌음. 추천해요
https://www.acmicpc.net/problem/33040
https://www.acmicpc.net/problem/33041
길이가 W인 수열들 H개로 탑을 쌓아 거신병을 만드는데, 위에 있는 수열의 원소들의 합이 아래에 있는 수열의 원소들의 합보다 크면 안 된다.
수열의 원소로는 C개의 1과 D개의 9가 존재하는데, C와 D를 남김없이 써야 한다.
개인적으로는 33041을 먼저 풀고 33040을 나중에 풀었다면 더 쉬웠을 것 같다. 33040의 문제풀이를 주류로 설명하도록 하겠다.
기본 아이디어
마지막에 for문을 이용해 한 행씩 출력하는데,
각 행에는 n개의 9와 W-n개의 1이 포함되어 있을 것이고 원소들이 출력되는 순서는 상관없는 문제이다.
그러니 각 행에 포함된 원소들을 벡터로 저장할 필요는 없다. 9의 개수나 1의 개수 둘 중 하나만 알고 있으면 모든 행을 출력할 수 있다.
잘못된 접근 : 등차수열과 등차수열의 합 공식
각 행에 포함된 9의 개수를 이용해 등차수열을 만들면 된다고 생각했다.
0,1,2,3,4,5,6,7,8,...,H-1의 등차수열을 만들어 놓으면 등차수열의 합 공식에 의해
H(H-1)/2로 계산할 수 있음.
여기다가 적절한 초항 A를 넣어주면 그 합은 AH+H(H-1)/2 로 계산할 수 있음.
여기다가 적절한 공차 d를 설정해 주면 그 합은 AH+dH(H-1)/2로 계산할 수 있음
근데 우리는 D(주어진 9 마작패)를 남김없이 써야 하니깐 등차수열의 초항과 공차를 적절히 조절한 뒤 남은 것들을 수열의 맨 마지막 원소에 짬처리하면 된다고 생각했다
위 아이디어로 초항과 공차를 적절히 조절하는 2중 for문을 짜서 시뮬레이션을 돌렸다. 예제는 통과했지만 내 코드로 안 돌아가는 케이스들을 많이 발견했고 코드를 다 지우고 새로 짜야 했다
올바른 접근
문제 조건을 만족할 수 있는 최소한의 수열을 만들어 놓고 그리디하게 하나씩 1마작패를 9마작패로 교체해주면 된다.
각 행에 포함된 9의 개수를 이용해 등차수열을 만드는데 벡터를 미리 만들어 놓는다.
0,1,2,3,4,5,6,7,8,...,H-1 의 원소를 갖는 벡터를 미리 만들어 놓았다. 이럴 경우 필요한 마작패의 개수는 등차수열의 합 공식에 의해 H(H-1)/2로 계산할 수 있음. H(H-1)/2 보다 D가 작다면 -1을 출력하고 return 0으로 프로그램을 바로 종료해 버린다.
이제 남은 할 일은 모든 행에 포함된 9마작패의 합이 D와 같아질 수 있도록 하는 것이다.
이 과정을 그리디하게 진행할 수 있다. 단순히 마작 거신병의 맨 아래층(수열의 가장 마지막 원소) 부터 인덱스를 앞으로 이동시키며 1 마작패를 9마작패로 바꿔 주면 된다.
v = {0,1,2,3,4,5,6,7,8,...,H-2, H-1} 에서
v = {0,1,2,3,4,5,6,7,8,..., H-2, H} 으로
v = {0,1,2,3,4,5,6,7,8,..., H-1, H} 으로
...
v = {1,2,3,4,5,6,7,8,9,..., H-1, H} 으로
v = {1,2,3,4,5,6,7,8,9,..., H-1, H+1} 으로
이런식으로 9 마작패를 하나씩 추가해주면서 모든 마작패 D를 소모한다
그리고 문제 조건을 만족하는지 확인해야 하는데, 마작 거신병의 모든 행에는 최대 W개의 마작패만 놓을 수 있으므로
D를 모두 소모했을 때 수열의 가장 마지막 원소가 W를 초과하는지 초과하지 않는지 체크해주면 된다.
만약 초과한다면 -1을 출력하고 바로 프로그램을 종료해 버린다
이후 이중 for문을 이용해 모든 행을 출력한다. 각 행마다 v[i]개의 9와 W-v[i]개의 1을 출력하면 된다.
코드
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
using namespace std;
int main(void){
fastio;
int H,W,C,D;cin>>H>>W>>C>>D;
vector<int> v(H);
int vsum=0;
for (int i = 0; i < H; i++)//가장 적은수의 9로 거신병을 만드는 조건
{
v[i]=i;vsum+=i;
}
if(vsum>D){cout<<-1;return 0;}
int offset = (D-vsum)/H;
int remain = (D-vsum)%H;
//이건 추가적인 아이디어인데, 루프를 돌리며 모든 D를 쓸 필요 없이
//나머지 연산으로 마지막 행 9 원소의 개수를 파악할 수 있다(시간복잡도를 크게 향상시킨다)
if(v[H-1]+offset+(remain>0)>W){cout<<-1;return 0;}//D를 다소모했는데 마지막 행이 W를 넘어버리면 종료
for (int i = H-1; i>=0; i--)
{
if(!remain)break;
v[i]++;remain--;
}
for (int i = 0; i < H; i++)
{
for (int j = 0; j < v[i]+offset; j++)
{
cout<<"9 ";
}
for (int j = 0; j < W-(v[i]+offset); j++)
{
cout<<"1 ";
}
cout<<"\n";
}
return 0;
}
33041번 문제의 코드로 확장
33041번 문제도 크게 다르지 않다. 다만 여기에서는 층마다 W값이 다르다.
접근 방법은 위 문제와 거의 똑같다.
1. 최소한의 9를 이용해 마작 거신병을 만들어 본 뒤 체크
2. 맨 아래층부터 9를 최대한 소모하며 위층으로 올라가기
3. 모든 D를 소모할 수 있는지 체크
4. 출력
과정 1을 쉽게 진행하기 위해선 일단 1 마작패로만 이루어진 거신병을 만들어 놓으면 된다. 이후 그냥 나이브하게 반복문 안에 반복문 집어넣고 1마작패들을 9 마작패들로 교체하면서 위 과정을 진행해 버리면 됨
33041번 문제의 코드
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
#define pii pair<int,int>
using namespace std;
int main(void){
fastio;
int H,C,D;cin>>H;
vector<int> W(H),v(H),vsum(H);
for (int i = 0; i < H; i++)
{
cin>>W[i];
vsum[i]=W[i];
}
cin>>C>>D;
//v[i]에 9의 개수를 적절히 집어넣기
for (int i = 1; i < H; i++)
{
int cnt = 0;//cnt개수만큼의 1을 9로 바꾸자
while ((vsum[i-1]>=vsum[i]+cnt*8)&&(cnt<=W[i]))
{
cnt++;
}
vsum[i]+=cnt*8;
v[i]+=cnt;
D-=cnt;
}
if(D<0){cout<<-1;return 0;}
//9를 최소로 사용하는 조건은 통과했음
while (W[H-1]>v[H-1]&&D>0)
{
v[H-1]++;D--;vsum[H-1]+=8;
}
for (int i = H-2; i >= 0; i--)
{
if(D==0)break;
while (W[i]>v[i]&&D>0&&vsum[i]+8<vsum[i+1])
{
v[i]++;
D--;
vsum[i]+=8;
}
}
if(D){cout<<-1;return 0;}
//D를 다 사용하는 조건은 통과했음
for (int i = 0; i < H; i++)
{
for (int j = 0; j < v[i]; j++)
{
cout<<"9 ";
}
for (int j = 0; j < W[i]-v[i]; j++)
{
cout<<"1 ";
}
cout<<"\n";
}
return 0;
}
애드혹은 가끔씩 풀어도 구성적(constructive) 문제만 보면 치를 떨었는데 이렇게 풀어보니 또 재밌는 것 같다