[SWEA/D4] 3234. 준환이의 양팔저울 - JAVA 자바

• 1066ms
• 순열 부분집합 DFS

양팔저울에 왼쪽 또는 오른쪽에 무게 추를 하나씩 올리는데 추를 올리는 과정에서 오른쪽이 왼쪽보다 무거워지면 절대 안된다는 것이 조건이다. 즉 추를 올리는 순서와 어느 쪽 저울에 추를 올릴지 고려해야한다.

 

추를 올리는 순서를 정하는 것은 순열, 올리는 순서가 정해진 추들을 어느쪽에 올릴 것인지 정하는 것은 부분집합을 이용하여 구현하였다.

 

추의 순서를 정한 후 부분집합을 통해 추들을 올렸을 때, 오른쪽무게가 왼쪽무게보다 커지지 않고 모든 추를 다 올렸으면 결과값++

 

문제가 헷갈릴 수 있어 꼼꼼하게 읽어봐야 이해하는 문제였다. 순열과 부분집합을 함께 이용하는 문제로 되게 괜찮은 문제라고 생각이 든다

 

# 소스코드

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

public class Solution {
    static int result, n;
    static int[] arr, numbers;
    static boolean[] selected;

    public static void subset(int cnt, int leftW, int rightW) {
        // 오른쪽 무게가 왼쪽 무게보다 무거워지면 바로 종료
        if(rightW > leftW) return;
        if(cnt == n) {
            result++;
            return;
        }
        // 왼쪽에 추를 올릴 경우
        subset(cnt+1, leftW + numbers[cnt], rightW );
        // 오른쪽에 추를 올릴 경우
        subset(cnt+1, leftW, rightW + numbers[cnt]);
    }

    public static void perm(int cnt) {

        if(cnt == n) {
            // 부분집합 구한 후 조건에 맞는지 확인
            // 맨 첫 추는 무조건 왼쪽이여야 함
            subset(1, numbers[0], 0);
            return;
        }
        for (int i = 0; i < n; i++) {
            if(!selected[i]) {
                selected[i] = true;
                numbers[cnt] = arr[i];
                perm(cnt+1);
                selected[i] = false;
            }
        }

    }

    public static void main(String[] args) throws IOException {
        // System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            n = Integer.parseInt(br.readLine());
            arr = new int[n];
            numbers = new int[n];
            selected = new boolean[n];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) 
                arr[i] = Integer.parseInt(st.nextToken());

            perm(0);

            sb.append('#').append(t).append(' ').append(result).append('\n');

        }
        System.out.println(sb);
    }
}

코드에 대한 피드백은 언제나 환영입니다🧚🏻‍♀️