https://www.acmicpc.net/problem/13300
문제
정보 초등학교에서는 단체로 2박 3일 수학여행을 가기로 했다. 여러 학년이 같은 장소로 수학여행을 가려고 하는데 1학년부터 6학년까지 학생들이 묵을 방을 배정해야 한다. 남학생은 남학생끼리, 여학생은 여학생끼리 방을 배정해야 한다. 또한 한 방에는 같은 학년의 학생들을 배정해야 한다. 물론 한 방에 한 명만 배정하는 것도 가능하다.
한 방에 배정할 수 있는 최대 인원 수 K가 주어졌을 때, 조건에 맞게 모든 학생을 배정하기 위해 필요한 방의 최소 개수를 구하는 프로그램을 작성하시오.
예를 들어, 수학여행을 가는 학생이 다음과 같고 K = 2일 때 12개의 방이 필요하다. 왜냐하면 3학년 남학생을 배정하기 위해 방 두 개가 필요하고 4학년 여학생에는 방을 배정하지 않아도 되기 때문이다.
| 학년 | 여학생 | 남학생 |
| 1학년 | 영희 | 동호, 동진 |
| 2학년 | 혜진, 상희 | 경수 |
| 3학년 | 경희 | 동수, 상철, 칠복 |
| 4학년 | 달호 | |
| 5학년 | 정숙 | 호동, 건우 |
| 6학년 | 수지 | 동건 |
입력
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 수학여행에 참가하는 학생 수를 나타내는 정수 N(1 ≤ N ≤ 1,000)과 한 방에 배정할 수 있는 최대 인원 수 K(1 < K ≤ 1,000)가 공백으로 분리되어 주어진다. 다음 N 개의 각 줄에는 학생의 성별 S와 학년 Y(1 ≤ Y ≤ 6)가 공백으로 분리되어 주어진다. 성별 S는 0, 1중 하나로서 여학생인 경우에 0, 남학생인 경우에 1로 나타낸다.
출력
표준 출력으로 학생들을 모두 배정하기 위해 필요한 최소한의 방의 수를 출력한다.
서브태스크
| 번호 | 배점 | 제한 |
| 1 | 2 | 입력 예시로 주어진 입력만 존재한다. |
| 2 | 10 | 1학년 남학생만 참가하는 것으로 가정한다. |
| 3 | 20 | 1학년만 참가하는 것으로 가정한다. |
| 4 | 68 | 원래의 제약조건 이외에 아무 제약조건이 없다. |
예제 입력1
16 2
1 1
0 1
1 1
0 2
1 2
0 2
0 3
1 3
1 4
1 3
1 3
0 6
1 5
0 5
1 5
1 6
예제 출력1
12
예제 입력2
3 3
0 3
1 5
0 6
예제 출력2
3
풀이
남학생, 여학생을 구분하여 모든 학생을 배정하기 위해 필요한 방의 최소 개수를 구해야 한다.
문제 예제를 눈대중으로 풀어보면 K(한 방에 배정할 수 있는 최대 인원수)가 2이니, 필요한 방 최소 개수는 12가 맞다.
이걸 어떻게 코드로 표현할까 생각해봤다.
특정 성별의 학년의 학생 수를 K로 나누면 몫과 나머지가 나온다.
예제 문제에서 3학년까지 몫과 나머지를 구해봤다. 규칙이 보였다.
나머지가 있으면(나머지가 0이 아니면) 필요한 방의 수는 (몫 + 1) 개이고,
나머지가 없으면 필요한 방의 수는 (몫)개이다.
이걸 코드로 표현하면 다음과 같다.
코드
internal class BOJ13300_방_배정
{
static void Main(string[] args)
{
string[] input1 = Console.ReadLine().Split(" ");
int N = int.Parse(input1[0]);
int K = int.Parse(input1[1]);
int[] menArray = new int[7];
int[] womenArray = new int[7];
for(int i = 0; i < N; i++)
{
string[] input = Console.ReadLine().Split(" ");
int S = int.Parse(input[0]);
int Y = int.Parse(input[1]);
if(S == 1)
{
menArray[Y] += 1;
}
else if(S == 0)
{
womenArray[Y] += 1;
}
}
int result = 0;
int quotient = 0;
int remainder = 0;
for (int i = 1; i < menArray.Length; i++)
{
quotient = menArray[i] / K;
remainder = menArray[i] % K;
if(remainder != 0)
{
result = result + quotient + remainder;
}
else
{
result = result + quotient;
}
quotient = womenArray[i] / K;
remainder = womenArray[i] % K;
if(remainder != 0)
{
result = result + quotient + remainder;
}
else
{
result = result + quotient;
}
}
Console.WriteLine(result);
}
}
문제
2점이 나왔다.
서브태스크가 있는 문제로, 부분 점수를 주는 것 같다.
원인
내 생각과 다르게 코드를 짰다.
나는 remainder가 0이 아닐 때, result = result + quotient + 1을 하도록 생각했었다.
그런데 코드는 result = result + quotient + remainder라고 적어서 틀렸다.
해결
result = result + quotient + remainder를 result = result + quootient + 1로 수정하니 100점을 맞아 통과했다.
코드
internal class BOJ13300_방_배정
{
static void Main(string[] args)
{
string[] input1 = Console.ReadLine().Split(" ");
int N = int.Parse(input1[0]);
int K = int.Parse(input1[1]);
int[] menArray = new int[7];
int[] womenArray = new int[7];
for(int i = 0; i < N; i++)
{
string[] input = Console.ReadLine().Split(" ");
int S = int.Parse(input[0]);
int Y = int.Parse(input[1]);
if(S == 1)
{
menArray[Y] += 1;
}
else if(S == 0)
{
womenArray[Y] += 1;
}
}
int result = 0;
int quotient = 0;
int remainder = 0;
for (int i = 1; i < menArray.Length; i++)
{
quotient = menArray[i] / K;
remainder = menArray[i] % K;
if(remainder != 0)
{
result = result + quotient + 1;
}
else
{
result = result + quotient;
}
quotient = womenArray[i] / K;
remainder = womenArray[i] % K;
if(remainder != 0)
{
result = result + quotient + 1;
}
else
{
result = result + quotient;
}
}
Console.WriteLine(result);
}
}
문제
Console.ReadLine()을 사용하니 백준에서 채점이 좀 느리다.
원인
Console.ReadLine()은 한 줄을 읽을 때마다 버퍼처리를 한다.
입력받을 데이터가 많을 수록 버퍼처리가 많아지고 속도가 느려진다.
Console.ReadLine()으로 Spllit을 N번 처리한다. 이러면 가비지 컬렉터(GC) 호출이 빈번해지고 속도가 느려진다.
해결
StreamReader는 내부적으로 큰 버퍼를 가지고 있다.
한 번에 많은 데이터를 읽어올 수 있다. StreamReader를 사용하면 해결된다.
코드
internal class BOJ13300_방_배정
{
static void Main(string[] args)
{
//string[] input1 = Console.ReadLine().Split(" ");
StreamReader sr = new StreamReader(Console.OpenStandardInput());
string[] input1 = sr.ReadLine().Split(" ");
int N = int.Parse(input1[0]);
int K = int.Parse(input1[1]);
int[] menArray = new int[7];
int[] womenArray = new int[7];
for(int i = 0; i < N; i++)
{
//string[] input = Console.ReadLine().Split(" ");
string[] input = sr.ReadLine().Split(" ");
int S = int.Parse(input[0]);
int Y = int.Parse(input[1]);
if(S == 1)
{
menArray[Y] += 1;
}
else if(S == 0)
{
womenArray[Y] += 1;
}
}
int result = 0;
int quotient = 0;
int remainder = 0;
for (int i = 1; i < menArray.Length; i++)
{
quotient = menArray[i] / K;
remainder = menArray[i] % K;
if(remainder != 0)
{
result = result + quotient + 1;
}
else
{
result = result + quotient;
}
quotient = womenArray[i] / K;
remainder = womenArray[i] % K;
if(remainder != 0)
{
result = result + quotient + 1;
}
else
{
result = result + quotient;
}
}
sr.Close();
Console.WriteLine(result);
}
}
복습1 풀이 (5/22)
남녀를 구분해야 하고, 같은 학년끼리 비교해야 하고, 최대 K명까지 방에 들어올 수 있다.
우선 남녀를 구분해야 배열을 만들면 되겠고, 이 배열로 학생수를 계산해서 하면.. 시간복잡도는 O(2N) = O(N)이 나오겠다.
이대로 풀어도 되겠다.
1. 학년별 남학생, 여학생 수를 저장하는 배열을 만든다. (menArray, womenArray)
2. 각 배열에서 학년별 필요한 방의 개수를 합산한다.
3. 정답을 출력한다.
코드1 - 오답
using System.Text;
public class BOJ13300
{
static StreamReader sr = new StreamReader(Console.OpenStandardInput());
static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
static StringBuilder sb = new StringBuilder();
static void Main(string[] args)
{
// 1. 남학생, 여학생 배열 만들기.
// 2. 각 배열에서 학년별 필요한 방의 개수 합산
// 3. 정답 출력
string[] input = sr.ReadLine().Split(" ");
int N = int.Parse(input[0]);
int K = int.Parse(input[1]);
int[] menArray = new int[7];
int[] womenArray = new int[7];
for(int i = 0; i < N; i++)
{
input = sr.ReadLine().Split(" ");
int n1 = int.Parse(input[0]); // 성별 (0 = 여, 1 = 남)
int n2 = int.Parse(input[1]); // 학년 (1 ~ 6)
if(n1 == 0)
{
womenArray[n2]++;
}
else if(n1 == 1)
{
menArray[n2]++;
}
}
int result = 0;
for(int i = 1; i < 7; i++)
{
if(menArray[i] > 0)
{
if(menArray[i] + 1 <= K)
result += 1;
else
result += (menArray[i] + 1) / K;
}
if(womenArray[i] > 0)
{
if(womenArray[i] + 1 <= K)
result += 1;
else
result += (womenArray[i] + 1) / K;
}
}
sb.Append(result);
sw.WriteLine(sb.ToString());
sr.Close();
sw.Close();
}
}
K가 3이고 3학년 남학생 수가 7이라면, 방은 3개가 필요하다. 그런데 위 코드는 2개가 나온다.
코드2 - 정답
using System.Text;
public class BOJ13300
{
static StreamReader sr = new StreamReader(Console.OpenStandardInput());
static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
static StringBuilder sb = new StringBuilder();
static void Main(string[] args)
{
// 1. 남학생, 여학생 배열 만들기.
// 2. 각 배열에서 학년별 필요한 방의 개수 합산
// 3. 정답 출력
string[] input = sr.ReadLine().Split(" ");
int N = int.Parse(input[0]);
int K = int.Parse(input[1]);
int[] menArray = new int[7];
int[] womenArray = new int[7];
for(int i = 0; i < N; i++)
{
input = sr.ReadLine().Split(" ");
int n1 = int.Parse(input[0]); // 성별 (0 = 여, 1 = 남)
int n2 = int.Parse(input[1]); // 학년 (1 ~ 6)
if(n1 == 0)
{
womenArray[n2]++;
}
else if(n1 == 1)
{
menArray[n2]++;
}
}
int result = 0;
for(int i = 1; i < 7; i++)
{
if(menArray[i] > 0)
{
result += menArray[i] / K;
if(menArray[i] % K > 0)
result += 1;
// if(menArray[i] + 1 <= K)
// result += 1;
// else
// result += (menArray[i] + 1) / K;
}
if(womenArray[i] > 0)
{
result += womenArray[i] / K;
if(womenArray[i] % K > 0)
result += 1;
// if(womenArray[i] + 1 <= K)
// result += 1;
// else
// result += (womenArray[i] + 1) / K;
}
}
sb.Append(result);
sw.WriteLine(sb.ToString());
sr.Close();
sw.Close();
}
}
조건식을 좀 수정했다.
총 학생수 / K를 result에 더하고, 총 학생수 % K > 0이면 result에 1을 더해줬다.
예전에 내가 짰었던 코드와 비슷한 것 같다.
'자료구조, 코딩테스트 > 배열(Array)' 카테고리의 다른 글
| [코딩테스트] BOJ 1919 - 에너그램 만들기 (성공) (0) | 2026.04.05 |
|---|---|
| [코딩테스트] BOJ 11328 - Strfry (실패) (0) | 2026.04.02 |
| [코딩테스트] BOJ 10807 - 개수 세기 (성공) (0) | 2026.03.31 |
| [코딩테스트] BOJ 3273 - 두 수의 합 (성공) (0) | 2026.03.30 |
| [코딩테스트] BOJ 1475 - 방 번호 (실패) (0) | 2026.03.25 |