백준 18233 러버덕을 사랑하는 모임 java (brute force, bit masking)

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

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

 

이번 문제는 사실 저번에 백트래킹으로 풀었던 적이 있는 문제다.

 

태그에 비트마스킹이 걸려 있어서 다른 접근으로 다시 풀었다. 고로 좋은 문제 (?)

 

 

 

아래는 백트래킹으로 접근한 방식

 

https://verycrazy.tistory.com/126

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

 

 

 

 

그리고 비트마스킹으로 풀었기 때문에 바로 이전 포스트에서 사용했던 코드를 재사용하고자 했다.

 

재사용이 가능한 문제여서 썼을 뿐 언제든 불가능할 수 있다 ㅎ...

 

비트 마스킹 개념이 모호해졌다면, 다시 한번 보고 오자.

 

https://verycrazy.tistory.com/142?category=1052323 

백준 2961 도영이가 만든 맛있는 음식 java (brute force, bit masking)

 

 

 

1. 비트마스킹을 통해 불 들어온 사람들만 따로 골라내 수를 센다. count에 저장.

for(int j=0; j<n; ++j){
    if((i & bits[j]) > 0){
        people[count] = j;
        ++count;
    }
}

 

 

 

2. 그리고 만약 카운팅한 사람 수와 목표 사람 수 p가 일치할 때 (count == p) 정답을 찾는 로직을 실행한다.

if(count == p){
    int leftSum=0, rightSum=0;
    for(int j=0; j<p; ++j){
        leftSum += ranges[people[j]][0];
        rightSum += ranges[people[j]][1];
    }

    if(leftSum <= e && e <= rightSum){
        ans = new int[n];
        solveOrNot = true;
        for(int j=0; j<p; ++j){
            ans[people[j]] = ranges[people[j]][0];
        }

        int amount = e - leftSum;
        int idx = 0;
        while (amount != 0){
            int diff = ranges[people[idx]][1] - ranges[people[idx]][0];
            if(diff <= amount){
                amount -= diff;
                ans[people[idx]] += diff;
            }
            else {
                ans[people[idx]] += amount;
                amount = 0;
            }
            ++idx;
        }

        for(int j=0; j<n; ++j){
            sb.append(ans[j]).append(" ");
        }
        break;
    }
}

정해진 사람 수만큼 나눠줘야 하기 때문에 무조건 같아야 한다. 

 

 

 

 

3. 미리 저장해두었던 people 인덱스 번호를 사용해서,

각 사람들의 left 범위값, right 범위값에 대한 총합을 구하고 e가 그 범위에 포함될 때 로직을 계속 진행

for(int j=0; j<p; ++j){
    leftSum += ranges[people[j]][0];
    rightSum += ranges[people[j]][1];
}

if(leftSum <= e && e <= rightSum){

	~ 계속 진행 ~

}

이 범위에 대한 값까지 뚫으면 정답을 찾은 것과 마찬가지이다. 한글로 풀어서 설명하면,

 

목표한 사람 수 p만큼 나눠줄 수 있고,

 

그 사람들에 대해 최소 개수 <= 나눠 주려는 총 개수 e <=  최대 개수 를 만족한 것이기 때문이다.

 

그래서 이제는 그냥 나눠주기만 하면 된다. 따라서 solveOrNot 플래그에 정답 체크를 미리 해둔다.

 

 

 

4. 먼저 최소치를 각 저장된 번호의 사람들에게 모두 나누어 준다. ans에 미리 저장한다.

for(int j=0; j<p; ++j){
    ans[people[j]] = ranges[people[j]][0];
}

 

 

 

5. 그러면 e - leftSum의 값만 남게 된다. 이 amount를 0번 사람부터 접근해서 알맞게 배분해주자.

int amount = e - leftSum;
int idx = 0;
while (amount != 0){
    int diff = ranges[people[idx]][1] - ranges[people[idx]][0];
    if(diff <= amount){
        amount -= diff;
        ans[people[idx]] += diff;
    }
    else {
        ans[people[idx]] += amount;
        amount = 0;
    }
    ++idx;
}

다만 그리디하게 매번 사람들을 만날 때마다 그 사람이 받을 수 있는 남은 범위에 대한 최대치까지 준다.

 

 

 

6. 정답을 sb에 저장시키고 출력한다. 끝.

for(int j=0; j<n; ++j){
    sb.append(ans[j]).append(" ");
}
break;

if(solveOrNot) System.out.print(sb);
else System.out.print(-1);

 

 

 

# 최종 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());

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

        int[] bits = new int[n];
        for(int i=0; i<n; ++i){
            bits[i] = 1 << i;
        }

        // bit masking (비트마스킹으로) + brute force (모든 경우의 수를 뽑아본다.) + greedy (뽑힌 사람들에게 최대치로 나누어주는 방향)
        int lth = 1 << n;
        int[] ans;
        boolean solveOrNot = false;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<lth; ++i){
            int count = 0;
            int[] people = new int[n];
            for(int j=0; j<n; ++j){
                if((i & bits[j]) > 0){
                    people[count] = j;
                    ++count;
                }
            }

            if(count == p){
                int leftSum=0, rightSum=0;
                for(int j=0; j<p; ++j){
                    leftSum += ranges[people[j]][0];
                    rightSum += ranges[people[j]][1];
                }

                if(leftSum <= e && e <= rightSum){
                    ans = new int[n];
                    solveOrNot = true;
                    for(int j=0; j<p; ++j){
                        ans[people[j]] = ranges[people[j]][0];
                    }

                    int amount = e - leftSum;
                    int idx = 0;
                    while (amount != 0){
                        int diff = ranges[people[idx]][1] - ranges[people[idx]][0];
                        if(diff <= amount){
                            amount -= diff;
                            ans[people[idx]] += diff;
                        }
                        else {
                            ans[people[idx]] += amount;
                            amount = 0;
                        }
                        ++idx;
                    }

                    for(int j=0; j<n; ++j){
                        sb.append(ans[j]).append(" ");
                    }
                    break;
                }
            }
        }

        if(solveOrNot) System.out.print(sb);
        else System.out.print(-1);

    }
}

당연히 속도는 백트래킹이 훨씬 빠르다.