[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) 문제만 보면 치를 떨었는데 이렇게 풀어보니 또 재밌는 것 같다