SWEA D4 3234 준환이의 양팔 저울

SWEA D4 3234 준환이의 양팔저울

 

 

문제링크

www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw&categoryId=AWAe7XSKfUUDFAUw&categoryType=CODE

SW Expert Academy

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

핵심 컨셉

고려사항

 * 좀 더 치밀한 가지치기가 필요한 상황
 * 1번 가지치기: 오른쪽의 무게가 왼쪽 보다 커서는 안된다. - 이건 쉽게 생각할 수 있고..
 * 2번 가지치기: 추를 올리는 과정에서 현재까지 오른쪽에 올려 놓은 추들의 무게 합이 어차피 남아있는 것들과 현재의 왼쪽 추들의 무게보다 크면 안된다.
  - 답으로 출력할 것이 경우의 수이기 때문에 이후의 상황은 그냥 경우의 수의 개수만 찾아보면 됨
  - 전체 경우의 수는 남은 추의 개수가 R일 때 R!*2^R (R개를 나열하는 경우의 수, 각각 오른쪽, 왼쪽에..)
  - 이때 추의 개수가 몇개 안되기 때문에 미리 구해놓고 사용해보자.

 * 1번 가지치기만 진행되는 경우는 static이면 시간초과, 로컬 변수면 겨우 통과, 2번 가지치기 하면 안전하게 통과

입력사항

* 무게추의 개수 N (1 ≤ N ≤ 9)

* 각 무게추의 무게를 의미하는 N개의 자연수가 공백으로 구분되어 주어진다. 무게는 1이상 999이하

출력사항

* 무게추를 올리는 과정에서 오른쪽 위에 올라가있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 커지지 않는 경우의 수를 출력

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

SWEA_D4_3234_준환이의양팔저울 (naver.com)

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package se.code.d4;

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

public class SWEA_D4_3234_준환이의양팔저울_DFS {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static StringTokenizer tokens = null;

    static int T;
    static int N;
    static int ans;
    // 미리 구해놓을 2의 거듭 제곱
    static int[] pow = new int[10];
    // 미리 구해놓을 factorial 값
    static int[] fac = new int[10];
    // 전체 추의 무게
    static int totalWeight;
    // 전체 추의 정보
    static int[] weights;

    static boolean[] visited;

    static void init() {
        pow[0] = 1;
        fac[0] = 1;
        for (int i = 1; i <= 9; i++) {
            pow[i] = pow[i - 1] * 2;
            fac[i] = fac[i - 1] * i;
        }
        // System.out.println(Arrays.toString(pow));
        // System.out.println(Arrays.toString(fac));
    }

    public static void main(String[] args) throws IOException {

        init();

        input = new BufferedReader(new StringReader(src));

        T = Integer.parseInt(input.readLine());
        for (int t = 1; t <= T; t++) {

            N = Integer.parseInt(input.readLine());
            weights = new int[N];
            visited = new boolean[N];

            totalWeight = 0;
            tokens = new StringTokenizer(input.readLine());
            for (int n = 0; n < N; n++) {
                weights[n] = Integer.parseInt(tokens.nextToken());
                totalWeight += weights[n];
            }

            // 입력 완료
            ans = 0;
            // 각 요소들을 배치해본다.
            perm(0, 0, 0, totalWeight);

            output.append("#").append(t).append(" ").append(ans).append("\n");
        }
        System.out.println(output);
    }

    // 올라가는 추들은 순서가 있다 --> 순열
    // 오른쪽 무게의 합이 왼쪽 무게의 합보다 커지지 않는 경우
    public static void perm(int idx, int leftSum, int rightSum, int remain) {
        // 남은 녀석을 모두 오른쪽에 놔도 왼쪽 무게 이하다.
        if (leftSum >= remain + rightSum) {
            ans += pow[N - idx] * fac[N - idx];
            return;
        }
        // 끝까지 가보면 필요 없징
        if (idx == N) {
            ans++;
            return;
        }
        // 아니면 재귀 진행
        for (int n = 0; n < N; n++) {
            if (!visited[n]) {
                // 이번 추를 사용해보자.
                visited[n] = true;
                int curWeight = weights[n];
                // 왼쪽에는 언제나 올릴 수 있음
                perm(idx + 1, leftSum + curWeight, rightSum, remain - curWeight);
                // 무게가 괜찮으면 오른쪽에도 놓아봄
                if (rightSum + curWeight <= leftSum) {
                    perm(idx + 1, leftSum, rightSum + curWeight, remain - curWeight);
                }
                // 이 추 말고 다른 추를 놔보자.
                visited[n] = false;
            }
        }
    }

    // END:

    static String src = "3\r\n" +
                        "3\r\n" +
                        "1 2 4\r\n" +
                        "3\r\n" +
                        "1 2 3\r\n" +
                        "9\r\n" +
                        "1 2 3 5 6 4 7 8 9";
}