준환이의 양팔저울 [SWEA 3234][JAVA][DFS]D4]

 

[광고 누르면 오늘의 행운 상승!!]

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

SW Expert Academy

문제의 저작권은 SW Expert Academy에 있습니다.

1. 참고사항
- DFS를 이용하여 왼쪽에 추를 더했을 때와 오른쪽에 추를 더했을때를 나누어 DFS를 돌린다.
- N까지 전부 돌리면 시간초과가 난다
- N-1까지 돌려주고 visit처리가 안된 추를 더해본다

2. 구현
- DFS를 이용하여 left, right 저울을 관리한다.
- 왼쪽저울에는 차례대로 추를 넣고 오른쪽저울에는 추를 더한 값이 left보다 낮으면 추를 넣는다.
- cnt가 N-1까지 반복했을때 종료하며 visit처리가 안된 추를 더해보고 left가 더 크다면 횟수를 증가시킨다.

package Study9;

import java.io.*;
import java.util.*;
public class 양팔저울 {
     
    public static int N;
    public static int[] chu;
    public static boolean[] visit;
    public static int tcnt;
     
    public static void main(String[] args) throws Exception {
    	System.setIn(new FileInputStream("test.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int tc = 1; tc <= T; tc++) {
           
            N = Integer.parseInt(br.readLine());
            chu = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i = 0; i < N;i++) {
            	chu[i] = Integer.parseInt(st.nextToken());
            }
            
            tcnt = 0;
            visit = new boolean[N];
            dfs(0,0,0);
             
            System.out.println("#" + tc + " " + tcnt);
        }
    }
    
    public static void dfs(int cnt, int left, int right) {
    	
    	if(cnt == N-1) {
            tcnt++;
            for(int i = 0 ; i < N; i++) {
                if(!visit[i] && left >= right+chu[i]) {
                    tcnt++;
                }
            }
            return;
        }
        
        for(int i = 0 ; i < N; i++) {
            if(!visit[i]) {
                visit[i] = true;
                dfs(cnt+1, left+chu[i], right);
                if(left >= right+chu[i])
                dfs(cnt+1, left, right+chu[i]);
                visit[i] = false;
            }
        }
    }
}