[Algorithm] 백준 13300 방 배정 (Python)

https://boj.kr/13300

이 문제는 그리 어렵지 않은 문제지만, 여러가지 해법이 있는게 재미있어서 글을 쓰게 되었습니다. 문제는 읽었다고 가정하고 진행하겠습니다.

어떤 그룹에서 사람 수를 N이라고 합시다. (음이 아닌 정수)

1. 사람 수를 K로 나눈 몫을 더하고, 나머지가 있는 경우 1을 더하기

인터넷을 찾아 보면 가장 일반적이고, 생각하기 쉬운 풀이입니다.
students = [[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]으로 초기화하고,
반복문을 통해 입력으로 S, Y를 받아 students[S][Y] += 1 해준 뒤
마지막에 반복문에서 각 배열값을 K로 나눈 몫과 나눴을 때 나머지가 있는 경우 1을 더한 값을 답에 더합니다.

2. 실수형으로 나누고 올림(ceill)

각 배열값을 K로 나눌 때 정수형이 아닌 실수형으로 나누고, 올림 하면 간단하게 풀립니다. 가령 K=5, N=27일 때  27/5 = 5.4, 이를 올림하면 필요한 방의 개수인 6이 나옵니다.

import math

N, K = map(int, input().split())
students = [[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]

for i in range(N):
    S, Y = map(int, input().split())
    students[S][Y-1] += 1

answer = 0
for i in range(6):
    answer += math.ceil(students[0][i] / K) + math.ceil(students[1][i] / K)
    
print(answer)

3. K-1 을 미리 더하고, 몫만 구하기

k = K - 1 이라고 할 때, 배열을 [[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]이 아니라 [[k, k, k, k, k, k], [k, k, k, k, k, k]]으로 초기화 하는 방법입니다.

어떤 값을 K로 나누면 그 나머지는 반드시 0 이상 K-1 이하입니다.
그리고 N(=사람 수)이 0 이상 K-1 이하이면 N//K = 0이고, N이 K 이상 2K-1 이하이면 N//K = 1입니다.
(* 여기서 'a//b' 표시는 a를 b로 나눈 몫을 의미합니다.)

그렇다면 사람 수에 (K-1)을 더한 값, N' = N + (K-1)의 경우는 어떨까요?
N이 0이면 N'//K = 0이고,
N이 1 이상 K 이하이면 N'//K = 1이며,
N이 K+1 이상 2K 이하이면 N'//K = 2이고,
좀 더 일반화 해서 어떤 음이 아닌 정수 n에 대해
N이 Kn+1 이상 K(n+1) 이하이면 N'//K = n이 됩니다.

이는 정확히 방을 배정하는 로직과 일치합니다.
사람이 0명이면 방을 0개,
사람이 1명 이상 K명 이하이면 방을 1개,
사람이 K+1명 이상 2K명 이하이면 방을 2개,
사람이 Kn+1명 이상 K(n+1)명 이하이면 방을 n개 주어야 하는 문제의 로직과 일치한다는 얘기입니다.

즉 모든 배열 값을 0이 아닌 k(=K-1)로 초기화함으로써 배열값이 N'이 되도록 하고, 이 배열값을 K로 나눈 몫을 구해주면 if 분기 없이도 우리가 원하는 방의 개수를 간단하게 얻을 수 있습니다.

K = 5인 경우로 표를 그려 생각하면 제가 무엇을 위해 배열값을 0이 아닌 k로 초기화한 것인지 조금 더 쉽게 이해할 수 있을 것입니다.

사람 수(N)	배열 값(N')	N' // K = 필요한 방 개수 (R)
0	K-1 = 4	4 // 5  = 0
1	K-1+1 = 5	5 // 5 = 1
2	K-1+2 = 6	6 // 5 = 1
4	K-1+4 = 8	8 // 5 = 1
5	K-1+5 = 9	9 // 5 = 1
6	K-1+6 = 10	10 // 5 = 2

 

N, K = map(int, input().split())
k = K-1
students = [[k, k, k, k, k, k], [k, k, k, k, k, k]]

for i in range(N):
    S, Y = map(int, input().split())
    students[S][Y-1] += 1

answer = 0
for i in range(6):
    answer += students[0][i] // K + students[1][i] // K
    
print(answer)

이렇게 수학적인 성질을 이용해서 구현하면 연산 수를 최소화할 수 있습니다.