방 배정하기( BOJ 14697 )

문제 : https://www.acmicpc.net/problem/14697

14697번: 방 배정하기

 

문제 파악하기

3개의 방에 N명의 학생들을 빈침대 없이 딱 떨어지게 배치할 수 있는지 판단하는 문제입니다. 단순히 가장 큰 방부터 넣는걸 생각하면 틀리는 문제입니다. 예를 들어 3개의 방에 침대가 각각 { 10, 8, 3 }개 있으며, 학생이 총 12명 있다고 생각해봅시다. 그러면 우리는 12명이니 3개의 침대가 있는 방 4개가 필요하다는 걸 알 수 있습니다. 하지만 우리가 설계한 [ 큰 방부터 넣는 알고리즘 ]에 따르면 학생을 배치할 수 없다는 결론에 도달합니다. 그렇다면 어떤 방법이 필요할까요?

 

문제 해결하기

이렇게 경우의 수 문제를 해결하는 가장 간단한 방법은 바로 모든 경우의 수를 세어보는 방법입니다. 완전탐색 혹은 브루트포스라고 하는 방법으로 나올 수 있는 모든 경우의 수를 테스트해보는 걸 의미합니다. 우리는 이 방법을 사용해 방에 학생들을 넣어서 N명을 넣을 수 있는지 확인해보겠습니다.

 

현재 방에 들어간 학생들의 수가 t라는 걸 나타내는 상태를 sv(t)라고 표현해보겠습니다. 현재 상태인 sv(t)가 될 수 있는 다음 상태는 총 3가지 있습니다. A, B, C방에 학생들을 넣는 경우입니다. 따라서 sv(t)는 sv(t-A) / sv(t-B) / sv(t-C)가 될 수 있습니다. 그럼 탐색을 언제까지 해야하는가? 그건 바로 t의 값에 달려있습니다. 만약 t가 0이라면 모든 학생을 딱 떨어지게 방법이 있다는 걸 의미하기에 1을 출력합니다. 만약 t가 0보다 작아진다면 해당 방법은 올바른 방법이 아니기에 0을 출력합니다. 위 방식대로 프로그래밍을 설계하면 다음과 같이 함수를 설계할 수 있습니다.

bool sv(int n) {
    if(n == 0) return dp[n] = 1;
    else if(n < 0) return 0;
    else return dp[n] = sv(n-A) | sv(n-B) | sv(n-C);
}

 

하지만 위 방법은 한 가지 문제가 있습니다. 중복된 sv(t) 계산으로 시간이 오래걸린다는 단점입니다. 예를 들어 각 방에 {1, 2, 3}명이 들어갈 수 있으며 현재 학생이 300명 있다면 탐색이 진행될수록 중복된 계산이 발생하게 됩니다. 그렇기에 한번 구한 값은 구하지 않도록 알고리즘을 개선하는 방법이 필요하며, 이 때 사용하는 건 바로 배열입니다. 배열을 사용하여 해당 계산의 결과를 저장하면 우리는 나중에 똑같은 계산을 할 필요 없이 배열에 저장된 값을 참고하면 알고리즘을 훨씬 개선할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#define NMAX 400
 
int A, B, C, N;
int dp[NMAX];
 
bool sv(int n) {
    if(n == 0) return dp[n] = 1;
    else if(n < 0) return 0;
    else {
        if(dp[n] >= 0) return dp[n];
        else return dp[n] = sv(n-A) | sv(n-B) | sv(n-C);
    }
}
 
int main() {
    scanf("%d %d %d %d", &A, &B, &C, &N);
 
    memset(dp, -1, sizeof(dp));
    printf("%d", sv(N));
}
 
/*
10 8 3 12
ans: 1
*/

후기

완전탐색 및 기본적인 메모이제이션을 해볼 수 있는 문제라고 생각합니다. 재귀함수를 이용한 완전탐색을 처음 배우는 사람에게 추천하고 싶은 문제입니다.