[SWEA] 3234번: 준환이의 양팔저울 (Java)
문제
SWEA(SW Expert Academy) 3234번 준환이의 양팔저울 [D4]
풀이
양팔저울에 올리는 순서 정하기 => 순열
어느쪽에 올릴지 정하기 => 부분집합
무게를 입력받아 우선 올려놓을 순서를 정함.
sorted배열에 실행완료 된 순열을 저장하며, 순열이 완성되었을 경우(cnt==N) 어느쪽에 올릴지 정함.
현재 추를 오른쪽에 올리는 경우, 왼쪽에 올리는 경우를 각각 실행.
실행도중 left<right일 경우, 가지치기를 통해 시간을 단축 (백트래킹)
기저조건을 만족한 경우, 경우의 수를 증가시킨 후 종료
코드
import java.io.*;
import java.util.*;
public class Solution{
static int N, res;
static int[] weight,sorted;
static boolean[] isSelected;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int tc = Integer.parseInt(br.readLine());
for(int T = 1 ; T<=tc ; T++) {
N = Integer.parseInt(br.readLine());
weight = new int[N];
sorted = new int[N];
isSelected = new boolean[N];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i =0 ; i < N ; i++) {
weight[i] = Integer.parseInt(st.nextToken());
}
res = 0;
perm(0);
sb.append("#").append(T).append(" ").append(res).append("\n");
}
System.out.println(sb.toString());
br.close();
}
//왼쪽, 오른쪽 관계없이 올려놓는 순서를 정하는 '순열'함수
private static void perm(int cnt) {
if(cnt == N) { //기저조건
scale(0,0,0);
}
//순열 만들기
for(int i = 0 ; i < N ; i++) {
if(isSelected[i]) continue;
sorted[cnt] = weight[i]; //sorted: 순열결과를 저장(인덱스 저장이 아닌 값 저장)
isSelected[i] = true; // 현재 인덱스 선택처리
perm(cnt+1);
isSelected[i] = false; // 선택 처리 초기화
}
}
//순열함수의 결과값을 이용해서 양팔저울에 올릴 경우의 수를 계산하는 '부분집합'함수
private static void scale(int cnt, int left, int right) {
if(left<right) return; //가지치기(현재 왼쪽의 무게보다 오른쪽의 무게가 많을 때)
if(cnt == N) { //기저조건
res++; //경우의 수 증가
return;
}
scale(cnt+1, left, right+sorted[cnt]); //오른쪽에 올렸을 때
scale(cnt+1, left+sorted[cnt], right); //왼쪽에 올렸을 때
}
}
Author And Source
이 문제에 관하여([SWEA] 3234번: 준환이의 양팔저울 (Java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dot2__/SWEA-3234번-준환이의-양팔저울-Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)