문제
초등학교 수학여행에서 N명의 학생을 방에 배정한다. 같은 학년, 같은 성별끼리만 한 방에 배정할 수 있고, 한 방에 최대 K명까지 들어갈 수 있을 때 필요한 최소 방의 수를 구하라.
입력
첫째 줄에 학생 수 N (1 이상 1,000 이하)과 방 최대 인원 K가 주어진다. 이후 N줄에 성별 S (0: 여, 1: 남)와 학년 Y (1~6)가 주어진다.
출력
필요한 최소 방의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 2 0 1 1 1 0 2 0 1 1 2 | 4 |
풀이
성별(2)×학년(6)의 2차원 배열로 학생 수를 집계한 뒤, 각 그룹별로 필요한 방 수를 올림 나눗셈으로 구한다.
- 2×7 크기의 배열(성별×학년)에 각 학생의 수를 집계한다
- 모든 (성별, 학년) 조합에 대해 ceil(학생 수 / K)를 계산한다
- 모든 그룹의 방 수를 합산하여 출력한다
핵심 아이디어: 학년과 성별이 같은 학생끼리만 방을 공유할 수 있으므로, 12개 그룹(2성별 × 6학년)으로 나누어 각각 독립적으로 방 수를 계산하면 된다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day08BOJ13300방배정 { // 13300
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int rooms = 0;
int[][] arr = new int[2][7];
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arr[m][y]++;
}
for (int i = 0; i < 2; i++) {
for (int j = 1; j < 7; j++) {
rooms += Math.ceil((double) arr[i][j] / K);
}
}
System.out.println(rooms);
br.close();
}
}복잡도
- 시간: O(N) — 학생 집계 후 12개 그룹 순회
- 공간: O(1) — 2×7 고정 크기 배열