[BOJ] 9037. The candy war.py.cpp

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

- 모두 동시에 사탕 절반을 오른쪽 아이에게 준다 -> 홀수개 사탕을 갖게 된다면 선생님이 한 개 더 줘서 짝수로

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

주어진 조건대로 잘 구현해주면 되는 문제이다.

#. Code

ㅇPython

T = int(input())
 
for i in range(T):
    N = int(input())
    b = [0] * (N + 1)
    child = list(map(int, input().split()))
    cnt = 0
 
    for c in range(N):
        if child[c] % 2 == 1:
            child[c] += 1
 
    while len(set(child)) != 1:
        for pos in range(N):
            b[pos + 1] = child[pos] // 2
            child[pos] -= child[pos] // 2
 
        b[0] = b[N]
 
        for pos in range(N):
            child[pos] += b[pos]
 
        for pos in range(N):
            if child[pos] % 2 == 1:
                child[pos] += 1
 
        cnt += 1
 
    print(cnt)

뭔가 파이썬의 장점을 잘 이용하지 못 하고 비효율적이게 짠 느낌이다...

for i in range(int(input())):
    N, child, cnt = int(input()), list(map(int, input().split())), 0
 
    while True:
        child = [i + 1 if i % 2 else i for i in child]
 
        if len(set(child)) == 1:
            print(cnt)
            break
 
        child = [child[i] // 2 + child[(i+1) % N] // 2 for i in range(N)]
        cnt += 1

더 간결하게 짠 코드지만, 강사님의 코드보다는 느리다..

ㅇC++

#include <cstdio>
 
int child[10], tmp[10];
int tc, n;
 
void teacher()
{
    int i;
    for (i = 0; i < n; i++)
    {
        child[i] /= 2;
        tmp[(i + 1) % n] = child[i];
    }
 
    for (i = 0; i < n; i++)
    {
        child[i] += tmp[i];
 
        if (child[i] & 1)
            child[i]++;
    }
}
 
bool check()
{
    int i;
    for (i = 0; i < n - 1; i++)
    {
        if (child[i] != child[i + 1])
            return false;
    }
 
    return true;
}
 
int main(void)
{
    int i, j, cnt;
 
    scanf("%d", &tc);
    while(tc--)
    {
        cnt = 0;
 
        scanf("%d", &n);
        for (j = 0; j < n; j++)
        {
            scanf("%d", &child[j]);
            if (child[j] & 1)
                child[j]++;
        }
 
        while (true)
        {
            if (check())
            {
                printf("%d\n", cnt);
                break;
            }
 
            teacher();
 
            cnt++;
        }
    }
 
    return 0;
}

#. Other Code

def teacher(N, candy):
    tmpLst = [0 for i in range(N)]
 
    for idx in range(N):
        if candy[idx] % 2:
            candy[idx] += 1
        candy[idx] //= 2
        tmpLst[(idx+1) % N] = candy[idx]
 
    for idx in range(N):
        candy[idx] += tmpLst[idx]
 
    return candy
 
def check(N, candy):
    for i in range(N):
        if candy[i] % 2 :
            candy[i] += 1
 
    return len(set(candy)) == 1
 
def process():
    N, candy = int(input()), list(map(int, input().split()))
    cnt = 0
 
    while not check(N, candy):
        cnt += 1
        candy = teacher(N, candy)
 
    print(cnt)
 
for i in range(int(input())):
    process()

line 32~33) test case 만큼 반복. 한 test case에 하나의 함수가 동작하도록 구현하면 편리

line 22~30) process()

line 26~28) 계속 사탕을 돌릴지 check 결과가 true일 경우,

line 27) 순환을 + 1

line 28) 선생님의 동작을 함수로 구현

line 15~20) 사탕을 계속 돌릴지 check하는 함수

line 16~18) 학생 수만큼 반복하면서 홀수개의 사탕을 가지고있는 학생에서 사탕 개수를 짝수개로 맞춰줌

line 20) 사탕을 모두 같은 개수로 가지고 있는지 bool 값을 return

line 1~13) 선생님의 동작을 구현한 함수

line 2) 학생 수만큼의 temp list

line 4~8) 모든 학생을 탐색

line 5~6) 홀수개의 사탕을 가지고 있는 학생의 사탕 개수를 짝수개로 맞춰줌

line 7) 사탕 개수를 반으로 

line 8) temp list에 절반인 사탕을 저장

   (idx + 1) % N 을 해주면서 n번째 학생의 경우 idx 0에 결과값을 저장하도록 설정

line 10~11) 절반 나눠준 사탕을 받는 과정

line 13) 갱신된 candy list return

#. Result

  - Input --------------------------------------------------------

4

5

2 4 7 8 9

1

9

6

10 5 13 2 7 8

4

3 4 4 3

------------------------------------------------------------------

  - Output --------------------------------------------------------

6

0

4

0

------------------------------------------------------------------