[BOJ 27502, 쉬움] 가난한 고흐와 붓 (C++)

개인적인 난이도

쉬움

 

인터랙티브 문제는 난이도에 비해 solved.ac 티어가 후하게 달리고, 풀면서 재미가 있다

 

인터랙티브 문제가 처음이라면??

이거 푸셈 : https://www.acmicpc.net/problem/23306

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

 

전략을 잘못 세워서 똑같은 이유로 2번 틀렸다

---

문제 이해 : 어떻게 하면 고흐를 가난하게(고흐가 붓을 많이 사용하게) 할 수 있을까?

일단 이 문제는 설명만 대충 읽어 보아도, 그래프 문제 같음

근데 몇 가지 경우만 따져봐도 답이 보인다

위 그림처럼 짝수개의 카드와 짝수개의 박스가 있다. 박스에 카드를 최대 한장씩 넣을 수 있고, 모든 카드를 박스에 넣어야 게임이 종료된다.

박스에다가 카드를 이렇게 넣었다고 하면, 그래프는 아래처럼 그려진다. 

직접 박스 배열에 카드를 넣으면서 그림을 그려보면 이해가 쉬울 것이다.

그 결과, N개의 정점과 N개의 간선이 그려지게 되고,

어떻게 그리든 간선은 1개의 사이클에 포함되어야 한다

 

문제 조건에 의해 필요한 붓의 개수 = 간선들을 한붓그리기하는데 필요한 획의 수 이다.

고흐는 한붓그리기 횟수를 적게 하도록 간선을 연결할 것이고,

나는 한붓그리기 횟수가 최대한 많아지도록 간선을 연결할 것이다.

 

실패한 풀이)

전략을 잘못 세웠다.

문제 조건에 의해 모든 간선은 1개의 사이클에 포함된다고 생각했고,

나는 사이클을 최대한 많이 만들면 한붓그리기 획 수가 최대가 된다고 생각했음.

사이클을 최대한 많이 만들기 위해서, 내 턴에는 항상 그 상자에 해당하는 인덱스의 카드를 상자에 집어넣도록 전략을 짰다.

고흐는 1-2-3-4-5-6-7... 이런식으로 간선들을 연결할 것이고

나는 8-8 9-9 10-10 11-11 이런식으로 간선을 연결하면 된다고 생각함

 

N=4, 6, 8조건에서 그림을 직접 그려보면서, 고흐 먼저 시작했을 때 N/2개의 사이클이 생기고, 나 먼저 시작하면 N/2+1개의 사이클이 생긴다고 생각했다. 

 

실패 코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;

int box[2001];
int card[2001];

int main(){
    fastio;
    int N,t;cin>>N>>t;//2000이하 짝수//t가 0이면 고흐부터 상자에 넣기
    int loops = N/2;
    if(t==0){
        cout<<"! "<<N/2<<endl;
        while (loops--)
        {
            int a,b;cin>>a>>b;//고흐턴
            box[b]=a;card[a]=b;


            int x,y;
            if(loops==0){
                for (int i = 1; i <= N; i++)
                {
                    if(card[i]==0){
                        x=i;
                    }
                    if(box[i]==0){
                        y=i;
                    }
                }
            }
            else{
                for (int i = 1; i <= N; i++)
                {
                    if(card[i]==0&&box[i]==0){
                        x=i;
                        y=i;
                        break;
                    }
                }
                
            }
            cout<<x<<" "<<y<<endl;//내턴
            box[y]=x;card[x]=y;
        }
    }
    else{
        cout<<"! "<<N/2+1<<endl;
        while (loops--)
        {
            int x,y;
            for (int i = 1; i <= N; i++)
            {
                if(card[i]==0&&box[i]==0){
                    x=i;
                    y=i;
                    break;
                }
            }
            cout<<x<<" "<<y<<endl;//내턴
            box[y]=x;card[x]=y;

            int a,b;cin>>a>>b;//고흐턴
            box[b]=a;card[a]=b;
        }
    } 
    return 0;
}

 

실패 이유)

근데 실패함

왜냐하면 내가 먼저 시작했을 경우, 아래같은 상황이 나올 수 있다.

고흐가 1-2-3-4-5... 이런식으로 간선을 순서대로 연결한다는 보장이 없음

고흐가 간선을 1-2 3-4 5-6... 이런식으로 두개씩 묶는다면 아래처럼 된다

 

1~6 순서대로 보면 된다

파란선 : 내 턴에 내가 한 거

빨간선 : 고흐턴에 고흐가 한 거

 

---

성공한 풀이)

훨씬 쉬운 전략이 있음

고흐가 간선을 어떻게 연결하든, 그걸 사이클로 만들어버리면 된다

고흐 먼저 시작할 경우

나 먼저 시작할 경우

 

고흐가 a카드를 b상자에 넣었으면, 내 턴에는 b카드를 a상자에 넣어버리면 된다. 이렇게 해도 마지막에 생성되는 사이클의 개수는,

내가 먼저 시작할 경우 : N/2 + 1개

고흐먼저 시작할 경우 : N/2개

로 동일하다

 

성공한 코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;

int box[2001];
int card[2001];

int main(){
    fastio;
    int N,t;cin>>N>>t;//2000이하 짝수//t가 0이면 고흐부터 상자에 넣기
    int loops = N/2;
    if(t==0){
        cout<<"! "<<N/2<<endl;
        while (loops--)
        {
            int a,b;cin>>a>>b;//고흐턴
            box[b]=a;card[a]=b;

            cout<<b<<" "<<a<<endl;//내턴
            box[a]=b;card[b]=a;
        }
    }
    else{
        cout<<"! "<<N/2+1<<endl;
        cout<<1<<" "<<1<<endl;
        int a,b,x,y;
        while (--loops)
        {
            cin>>a>>b;//고흐턴
            box[b]=a;card[a]=b;
            
            cout<<b<<" "<<a<<endl;//내턴
            box[a]=b;card[b]=a;
        }
        cin>>a>>b;
    } 
    return 0;
}