백준 (BOJ) 18233 러버덕을 사랑하는 모임 java 백트래킹

https://www.acmicpc.net/problem/18233

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

 

구상부터 시작해서 실제 코드를 짜는데 어려움이 많았던 문제.

 

실버 1이라길래, 다소 편한 마음으로 임했다가 명치 정통으로 맞았다.

 

쉽다는 의견들도 많은데, 개인적으로는 난이도 분배가 좀 ㅎ....

 

 

 

1. 첫 접근은 대강 '조합'을 이용해서 어떻게 해야 하는지 감을 잡을 수 있다. 20C10 --> 약 18만 번 --> brute force 가능

 

2. 각 정답 후보군의 탐색 횟수를 줄이기 위해 backtracking이 가능하다는 걸 알게 된다.

 

3. backtacking을 위한 recursive 돌리기

 

4. 또한 backtracking을 하기 위한 약간의(?) stack 개념 --> 후보군이 얼마만큼 쌓였느냐를 통해 (주어진 P에 맞춰) 더 쌓을 것인지 아니면 정답 판별을 할 것인지 결정한다. top을 쓰는 풀이도 있던데 써도 되고 안 써도 되지 싶다.

 

5. 정답을 찾는 즉시 모든 재귀 층을 무너뜨려야 하므로 flag (변수명: stopTrigger) 삽입하고, 종료 조건문도 각 재귀 반복 후의 지점에 삽입

 

6. 또한 각 탐색 시점마다 골라진 사람들의 총 min과 max의 값이 다르므로 사전에 계산해주어야 한다.

 

 

 

다음에 다시 풀어봐야지..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, P, E;
    static int[][] arr;
    static int[] stack, lava;
    static boolean stopTrigger;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken()); // Person, 줄 사람 수
        E = Integer.parseInt(st.nextToken()); // 총 선물할 인형 수

        arr = new int[N][2];
        stack = new int[P];
        lava = new int[N];

        for(int i=0; i<N; ++i){
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        backtracking(0, 0);
        StringBuilder sb = new StringBuilder();
        for(int a : lava){
            sb.append(a).append(" ");
        }
        System.out.println(stopTrigger ? sb : -1);

    }

    static void backtracking(int count, int s){
        if(P != count){
            for(int i=s; i<N; ++i){ // 해당 자릿수에 대한 backtracking 진행
                stack[count] = i;
                backtracking(count+1, i+1);
                if(stopTrigger){
                    return;
                }
            }
        }
        else{ // P == count
            int min=0, max=0;
            for(int i=0; i<P; ++i){
                min += arr[ stack[i] ][0];
                max += arr[ stack[i] ][1];
            }

            if(E < min || max < E){ // 범위 체크
                return; // 싯빠이
            }

            stopTrigger = true;
            int diff = E - min;

            for(int i=0; i<P; ++i){
                lava[stack[i]] += arr[ stack[i] ][0];
                if(diff != 0){
                    int remained = arr[ stack[i] ][1] - arr[ stack[i] ][0];
                    if(remained < diff){
                        lava[stack[i]] += remained;
                        diff -= remained; // diff 깎아 먹고
                    }
                    else {
                        lava[stack[i]] += diff;
                        diff = 0;
                    }
                }
            }
        }
    }
}