[백준] 18233 러버덕을 사랑하는 모임

문제 주소 : www.acmicpc.net/problem/18233

18233번: 러버덕을 사랑하는 모임

문제 확인

 

간단한 dfs 문제입니다. 통과는 간단하지만 시간과 메모리 단축을 하기 위해서는 조금 생각해야 할 것이 있습니다.

1. dfs 탐색 횟수 줄이기
2. dfs 함수의 인자 수 줄이기
3. 조건에 부합하는지 확인하는 함수를 dfs와 분리하여 dfs 함수 크기 줄이기
4. 조건 확인 시 루프 문 최소화

풀이

 

stack을 이용하여 p개만큼 사람을 선택 해 조건에 부합하는지 확인을 합니다.

이때 dfs 탐색 수를 줄이기 위하여 i : stack[top-1] + 1 ~ n - (p - top) 까지 탐색을 합니다.

stack[top-1]의 의미는 전 단계의 수이며 n-(p-top)의 의미는 현재 탐색할 수 있는 최대 인덱스입니다.

예를 들어 n = 8, p = 4 : 8명중 4명을 선택해서 인형을 보내줘야 할 때 (0 1 2 3), (0 1 2 4), (0 1 2 5) ... (5 6 7 8)을 탐색해야 할 것입니다.

처음 0을 선택했을 때 다음 칸에 올 수 있는 수는 전 단계의 다음 숫자(=stack[top-1] + 1)인 1부터 8이지만 8까지 다 탐색을 하게 되면 중복이 발생하게 되고 이를 방지하며 탐색 횟수를 줄이기 위해 현재 남은 사람의 수(=p-top)를 빼 주어 탐색합니다.

 

조건에 부합하는지 확인하기 위해서는 left의 모든수, right의 모든 수를 더해봅니다.

total_left<=e && e<=total_right이 성립하면 e를 만족할 수 있는 집합이 존재한다는 의미입니다.

배열을 left 수에 맞춰서 초기화 해 주고 정확히 e를 맞춰주기 위해 나머지를 적당히 분배해 줍니다.

이때 조건 루프문을 최소화하기 위해 1씩 분배하지 않고 right을 넘지 않도록 조정하면서 늘려줍니다.

 

* 컴파일러가 최적화 하면서 조건 검사 함수를 dfs에 넣어버리는 경우가 있습니다. 이때 증가하는 메모리를 방지하기 위해 전역 변수를 사용하거나 최적화를 꺼 주면 됩니다.

 

코드

#include <cstdio>
#include <cstdlib>
#include <string.h>
typedef struct node {
    int left, right;
}node;
int n, p, e;
node ary[20];
int stack[20], top;
int c[20] = { 0 };
int left = 0, right = 0;
void check() {
    memset(c, 0, sizeof(c));
    left = right = 0;
    for (int i = 0; i < p; i++) {
        left += c[stack[i]] = ary[stack[i]].left;
        right += ary[stack[i]].right;
    }
    if (left <= e && e <= right) {
        for (int i = 0; i < n; i++) {
            if (c[i]) {
                int gap = ary[i].right - ary[i].left;
                if (left + gap < e) {
                    left += gap;
                    c[i] += gap;
                }
                else {
                    c[i] += e - left;
                    for (int j = 0; j < n; j++)
                        printf("%d ", c[j]);
                    exit(0);
                }
            }
        }
    }
}
void dfs(int cur) {
    if (top == p) {
        check();
    }
    else if (cur < n) {
        for (int i = top > 0 ? stack[top - 1] + 1 : 0; i < n - (p - top) + 1; i++) {
            stack[top++] = i;
            dfs(cur + 1);
            --top;
        }
    }
}
int main() {
    scanf("%d%d%d", &n, &p, &e);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &ary[i].left, &ary[i].right);
    dfs(0);
    printf("-1");
}