[알고리즘 2단계] 방 배정하기-완전 탐색 (Brute-Force)

[출처 : Goorm 사이트 - 웃긴 뽑기]

문제

정보 초등학교 6학년 여학생들(중학교 3학년 남학생들)은 단체로 2박 3일 수학여행을 가기로 했다. 학생들이 묵을 숙소에는 방의 정원(방 안에 있는 침대 수)을 기준으로 세 종류의 방이 있으며, 같은 종류의 방들이 여러 개 있다. 정보 초등학교에서는 학생들에게 이 방들을 배정하되, 배정된 모든 방에 빈 침대가 없도록 하고자 한다.

 

예를 들어, 방의 종류가 5인실, 9인실, 12인실이고 6학년 여학생 전체가 113명이라면, 5인실 4개, 9인실 5개, 12인실 4개를 예약하면 각 방에 남는 침대 없이 배정이 가능하다. 또한 12인실은 사용하지 않고 5인실 10개와 9인실 7개만 사용하는 것도 가능하다. 그러나 방의 종류가 3인실, 6인실, 9인실이고 6학년 여학생 전체가 112명이라면 빈 침대 없이 방을 배정하는 것은 불가능하다.

 

방의 정원을 나타내는 서로 다른 세 자연수와 전체 학생 수를 나타내는 자연수 하나가 주어졌을 때, 배정된 모든 방에 빈 침대가 없도록 방 배정이 가능한지를 결정하는 프로그램을 작성하시오.

 

단, 세 종류의 방은 모두 충분한 개수가 있다고 가정하며, 위의 예에서와 같이 세 종류의 방을 모두 활용하지 않고 한 종류 또는 두 종류의 방만 이용하여 배정하는 것도 허용한다.

 

입력 형식

표준 입력으로 방의 정원을 나타내는 서로 다른 세 자연수 A, B, C (1 ≤ A < B < C ≤ 50)와 전체 학생 수를 나타내는 자연수 N (1 ≤ N ≤ 300)이 공백으로 분리되어 한 줄에 주어진다.

 

출력 형식

빈 침대 없이 배정이 가능할 경우 표준 출력으로 1을, 불가능할 경우 0을 출력한다.

 

부분문제의 제약 조건

● 부분문제 1: 전체 점수 100점 중 3점에 해당하며 입력 예시로 주어진 입력만 존재한다.

● 부분문제 2: 전체 점수 100점 중 5점에 해당하며 A=1이다.

● 부분문제 3: 전체 점수 100점 중 14점에 해당하며 B, C는 A의 배수이다.

● 부분문제 4: 전체 점수 100점 중 78점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.

 

 

---

풀이

DP 로도 풀수 있는 문제라고 하는데 아직 동적계획법에 대한 응용력이 부족하다.

그래서 컴퓨터의 연산능력을 이용하는 완전탐색(Brute-Force) 방법을 이용하였다.

완전탐색(Brute-Force) 방법

: 모든 경우의 수를 다 해보는 것이다. 알고리즘을 풀 때 강력한 방법이지만, 시간은 최대로 들어간다.

- for문 사용

- 순열 조합 사용

- 재귀함수 사용

- 비트마스크 사용

등의 방법이 있다.

코드

#include <stdio.h>

int main() {
	int a, b, c, total;
	scanf("%d %d %d %d", &a, &b, &c, &total);
	
	int a_lim = total/a;
	int b_lim = total/b;
	int c_lim = total/c;

	for (int i=0; i <= c_lim; i++) {
		int cur = c * i;
		for (int j=0; j <= b_lim; j++) {
			int cur2 = cur + j*b;
			for (int k=0; k <= a_lim; k++) {
				int cur3 = cur2 + k*a;
				 if (cur3 == total) {
					printf("1");
					return 0;
				}
			}
		}
	}
	printf("0");
	return 0;
}

반복문을 찬찬히 따라가면 모든 경우의 수를 연산하는 것을 알 수 있다.

결과

 

---

* 개인적인 학습 목적으로 작성한 글이기에 내용에 잘못된 정보가 있을 수 있습니다.

* 문제 출처 - level.goorm.io/exam/48128/방-배정하기/quiz/1