방 배정(초등) > 문제은행

본문 바로가기


문제은행

2991 : 방 배정(초등)

제한시간: 1Sec    메모리제한: 32mb
해결횟수: 131회    시도횟수: 247회   



정보 초등학교에서는 단체로 2박 3일 수학여행을 가기로 했다. 여러 학년이 같은 장소로 수학여행을 가려고 하는데 1학년부터 6학년까지 학생들이 묵을 방을 배정해야 한다. 남학생은 남학생끼리, 여학생은 여학생끼리 방을 배정해야 한다. 또한 한 방에는 같은 학년의 학생들을 배정해야 한다.
물론 한 방에 한 명만 배정하는 것도 가능하다. 한 방에 배정할 수 있는 최대 인원 수 K가 주어졌을 때, 조건에 맞게 모든 학생을 배정하기 위해 필요한 방의 최소 개수를 구하는 프로그램을 작성하시오.

예를 들어, 수학여행을 가는 학생이 다음과 같고 K = 2 일 때 12개의 방이 필요하다. 왜냐하면 3학년 남학생을 배정하기 위해 방 두 개가 필요하고 4학년 여학생에는 방을 배정하지 않아도 되기 때문이다.
42c64e0d7641f00316b79c17072e1a4a_1470811

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 수학여행에 참가하는 학생 수를 나타내는 정수 N(1 ≤ N ≤ 1,000)과 한 방에 배정할 수 있는 최대 인원 수 K(1 ≤ K ≤ 1,000)가 공백으로 분리되어 주어진다. 다음 N 개의 각 줄에는 학생의 성별 S 와 학년 Y(1 ≤ Y ≤ 6)가 공백으로 분리되어 주어진다. 성별 S 는 0, 1중 하나로서 여학생인 경우에 0, 남학생인 경우에 1로 나타낸다.


표준 출력으로 학생들을 모두 배정하기 위해 필요한 최소한의 방의 수를 출력한다.

부분문제의 제약 조건
• 부분문제 1: 전체 점수 100점 중 2점에 해당하며 입력 예시로 주어진 입력만 존재한다.
• 부분문제 2: 전체 점수 100점 중 10점에 해당하며 1학년 남학생만 참가하는 것으로 가정한다.
• 부분문제 3: 전체 점수 100점 중 20점에 해당하며 1학년만 참가하는 것으로 가정한다.
• 부분문제 4: 전체 점수 100점 중 68점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.

[Copy]
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
[Copy]
12


[Copy]
3 3
0 3
1 5
0 6
[Copy]
3




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.