• TOC {:toc}

이 글은 백준 온라인 저지의 9037번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.08.10 (Python)

메모리 시간 코드 길이
31312 KB 100 ms 475 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 21:39:58 21:42:03
풀이 생각 21:50:28 22:07:52
코딩 22:08:07 22:30:50 
from math import ceil

def is_diff(candy):
    avg = sum(candy) // len(candy)
    for x in candy:
        if x != avg:
            return True
    return False


for _ in range(int(input())):
    N = int(input())
    candy = [ceil(i / 2) for i in map(int, input().split())]
    count = 0

    while is_diff(candy):
        tmp = []
        for i in range(N):
            tmp.append(ceil((candy[i] + candy[i - 1]) / 2))
        count += 1
        candy = tmp

    print(count)

아이디어 & 풀이

예제 입력 1의 첫 번째 테스트 케이스의 진행은 다음과 같다.

count 0 1 2 3 4 5 6
반 나눈 값 1 2 4 4 5 3 2 3 4 5 4 3 3 4 5 5 4 3 4 5 5 5 4 4 5 5 5 5 4 5
오른쪽에 준 후 2 4 7 8 9 6 3 6 8 9 8 5 5 7 9 9 7 6 7 9 10 9 7 7 9 10 10 9 8 9 10 10 10 9 9
짝수개로 보충 2 4 8 8 10 6 4 6 8 1 8 6 6 8 10 10 8 6 8 10 10 10 8 8 10 10 10 10 8 10 10 10 10 10 10

사탕을 추가해 짝수개로 만든 뒤 2로 나누는 것을 ceil을 이용해 구현한다.

  • 2로 나눈 뒤 소수점 마지막 자리에서 올림 하면 홀수 개의 사탕을 짝수 개로 만든 뒤 2로 나눈 것과 같다.
  • ceil(candy / 2)
  • 처음 사탕의 수를 입력받을 때 이 과정을 거쳐 입력받으면 편하다.

0 ~ N - 1 까지 순회하면서 사탕의 수를 계산한다.

  • 이전 원소와 현재 원소를 더한 뒤 2로 나눈 값을 올림 한다.
  • i가 0일 경우 i - 1은 -1이고 이는 마지막 원소를 가리키므로 문제 조건에 부합한다.

피드백

  • 리스트 컴프리헨션을 이용해 리스트를 생성한 뒤 현재 리스트 C에 대입하면 tmp가 없어도 된다.

2023.02.17 (JS)

메모리 시간 코드 길이
10892 KB 208 ms 975 B 
const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [T, ...lines] = input;

function isCandyEqual(candies) {
    const avg = parseInt(candies.reduce((a, b) => a + b, 0) / candies.length);
    for (const candy of candies) {
        if (candy !== avg) {
            return false;
        }
    }

    return true;
}

function toEven(n) {
    return n % 2 ? n + 1 : n;
}

function main() {
    for (let i = 0; i < T; i += 1) {
        const N = parseInt(lines[i * 2]);

        let count = 0;
        let candies = lines[i * 2 + 1].split(" ").map((n) => toEven(parseInt(n)));

        while (!isCandyEqual(candies)) {
            const newCandies = [];
            for (let j = 0; j < N; j += 1) {
                newCandies.push(Math.ceil(toEven((candies[j] + candies[(j - 1 + N) % N]) / 2)));
            }
            candies = newCandies;
            count += 1;
        }
        console.log(count);
    }
}

main();

참고 답안

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    N, count = int(input()), 0
    C = list(map(int, input().split()))
    while True:
        # 짝수가 아니면 올림해 짝수로 만들어 주는 과정
        C = [i if i % 2 == 0 else i + 1 for i in C]
        if len(set(C)) == 1:
            print(count)
            break
        C = [C[i] // 2 + C[(i + 1) % N] // 2 for i in range(N)]
        count += 1

아이디어 & 풀이

  • 모든 원소가 같은지를 set 자료구조를 이용해 확인한다.
    • 리스트의 모든 원소의 값이 같으면 해당 리스트를 set으로 만든 결과의 원소는 1개이다.
    • len(set(C)) == 1인지 확인하면 된다.