[TIL] 백준 13300번: 방 배정 (Python) - 시간 복잡도 O(N)으로 풀기

문제 링크:  https://www.acmicpc.net/problem/13300

13300번: 방 배정

  풀이 방법

1. 남학생 여학생 배열 생성
2. 각 학년 인덱스에 대해 인원 저장 (0번 ~ 5번: 1학년 ~ 6학년)
3. 두 배열을 이어 붙여 loop돌며 K로 나누어 떨어지면 몫 만큼, 나머지가 있을경우 몫 + 1 만큼 방 수 증가

남학생 (1학년 ~ 6학년)

0	0	0	0	0	0

여학생 (1학년 ~ 6학년)

0	0	0	0	0	0

예제 입력2에 대한 결과는 아래와 같다.

남학생

0	0	0	0	1	0

여학생

0	0	1	0	0	1

방 수를 셀 경우 두 배열을 이어붙인 아래 배열을 돌며 K=3으로 나누며 카운트를 더한다.

0	0	0	0	1	0	0	0	1	0	0	1

 

  첫 코드

import sys

N, K = map(int, sys.stdin.readline().strip().split())
arr = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]

boys = [0] * 6
girls = [0] * 6
room = 0

for gender, grade in arr:
    if gender == 0:
        girls[grade-1] += 1
    else:
        boys[grade-1] += 1

for i in boys + girls:
    if i:
        room += i//K + 1 if i%K else i//K

print(room)

 

  코드 보완

나머지가 있을 경우 + 1, 없을 경우 몫만 사용하는 코드는 math.ceil을 이용하여 반올림하도록 하면 된다.

import math

for i in boys + girls:
    if i:
        room += math.ceil(i/K)