[C++] 백준 9037 The candy war

www.acmicpc.net/problem/9037

9037번: The candy war

 

1. 서론

 

이해만 한다면 쉽게 풀 수 있는 문제. 근데 좀 헷갈려서 이해하는데 좀 걸림 ㅎ

 

2. 문제 풀이

 

n명에게 사탕이 주어진다. 사탕 절반을 각각 옆 사람에게 넘겨준다. 넘겼을 때 사탕이 홀수인 사람이 있으면 1개를 더 줘서 짝수로 만든다. 이걸 순환이라고 부르며 이 경우에 1씩 count 해준다. 위와 같은 과정을 반복한 후, n명이 모두 같은 수의 사탕을 갖게 되었을 때 몇 번의 순환을 했는지를 구하는 문제이다. 

 

처음에는 사탕을 절반씩 주는 것을 오해했다. 전원이 동시에 반을 옆 사람에게 주는 게 아니라 1번이 2번에게 반을 준 경우, 2번이 3번에게 반을 준 경우... 이런 식으로 이해해서 시간 낭비를 했고, 받은 사람만 사탕을 홀수에서 짝수로 주나, 준 사람 받은 사람 둘 다 주나 이런 걸로도 고민했었다 ㅎ... 문제는 전원이 동시에 사탕을 나누는 것이었고, 그렇게 한 턴이 끝나면 홀수개의 사탕을 가지고 있는 사람에게 사탕을 보충해주는 것이다.

 

여러 시행착오 끝에 결국엔 이렇게 풀었다.

문제의 조건대로 처음에 입력받았을 때 홀수가 있는지 체크하고, 있는 경우 사탕을 채워준다.

그리고 값이 바뀌었을 때 모든 사람이 가지고 있는 사탕 개수가 같은지 체크해준다.

같지 않은 경우 반복문을 통해 로직을 실행한다.

배열을 하나 만들어 원래의 값에서 절반의 값을 배열에 넣어준다.

그리고 그 배열에 원래의 배열의 절반의 값을 더해준다. 이 경우 옆 사람에게 사탕의 절반을 받는 것이기 때문에 index를 +1 한 값의 절반을 받는다. 이렇게 한 턴이 끝나면 또 홀수가 있는지 체크해주고 순환의 개수도 count 해준다. 그리고 모두가 같은 수의 사탕을 가졌는지 확인한다.

 

3. 코드 설명

 

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    int n, c, cnt = 0, i, j, t, f = 0;

    cin >> n;

    for (i = 0; i < n; i++)
    {
        cin >> c;

        vector<int> v;

        for (j = 0; j < c; j++)
        {
            cin >> t;
            if (t % 2 != 0) t++;
            v.push_back(t);
        }

        t = v[0];
        for (j = 1; j < c; j++)
            if (t != v[j])
                f = 1;
        
        if (f == 1) 
        {
            while(1)
            {
                vector<int> tmp;

                tmp.push_back(v[c - 1] / 2);
                for (j = 0; j < c - 1; j++)
                    tmp.push_back(v[j] / 2);

                for (j = 0; j < c; j++)
                    tmp[j] += v[j] / 2;

                for (j = 0; j < c; j++)
                {
                    if (tmp[j] % 2 != 0)
                    {
                        tmp[j]++;
                        f = 1;
                    }
                }

                if (f == 1) cnt++;
                f = 0;

                t = tmp[0];
                for (j = 1; j < c; j++)
                    if (t != tmp[j])
                        f = 1;

                if (f == 0) break;
                v = tmp;
            }
        }

        cout << cnt << endl;
        cnt = 0, f = 0;
    }
}

 

이 코드를 짤 때 진짜 얼빠진 짓을 했다. j를 i라고 적어놓고 안 돌아가서 난리가 났던... 절대 다시는 하고 싶지 않은 실수 1위.

값들을 입력받는다. v는 입력 받은 사탕의 값들이다. 홀수일 경우 +1을 해줘서 값을 전부 짝수로 맞춰준다.

그리고 반복문에서 값을 맞춰준다. tmp는 값들을 바꾸기 위해서 잠깐 사용하는 임시 배열이다.

f를 사용해서 순환을 count 해준다. 그리고 뒤에서 전부 같은 값인지 확인하기 위해서도 f를 사용한다. 0인지 1인지를 이용해서 확인하는 것이기 때문에 중간중간 초기화를 해주는 것이 중요하다.