백준 온라인 저지 1653 양팔 저울
문제
무게가 서로 다른 추들의 집합이 주어진다. 각 추의 무게는 1g 이상 9g 이하의 정수이다. 이 추들 중에서 몇 개를 선택하여 양팔저울에 올려서 평형을 만들고자 한다. 양팔저울에는 양쪽에 5개씩 등간격의 눈금이 표시되어 있고 추는 눈금 위에만 놓일 수 있다. 한 눈금 위에는 하나의 추만이 놓일 수 있다. 예를 들어, {2, 3, 4, 5, 9}가 추 집합으로 주어졌을 때, 아래 그림과 같이 왼쪽에는 2g짜리 추를 중심에서 3 떨어진 자리에 놓고, 오른쪽에는 3g짜리 추를 중심에서 2 떨어진 자리에 놓으면 저울은 평형을 이루게 된다. (2×3=3×2)
위와 동일한 추 집합에서, 아래 그림과 같이 양쪽에 서로 다른 수의 추를 배치해서 평형을 이룰 수도 있다. (4×4+2×2=5×4)
두 그림과 같이 저울이 평형을 이룬 경우, 추가 놓인 모양에 따라 대응되는 하나의 숫자를 다음과 같이 생성한다. 추가 놓이지 않은 빈 눈금에는 0이 들어가고 추가 놓인 눈금은 그 추의 무게에 해당하는 숫자가 들어간다. 단, 이렇게 만들었을 때 0이 아닌 첫 숫자가 나타나기까지의 왼쪽에 있는 모든 0은 제거한다. 예를 들면, 첫 그림에 대응되는 숫자는 20003000이 되고, 둘째 그림에 해당되는 숫자는 402000050이 된다. 이렇게 하면 양팔저울이 평형을 이루는 추의 배치 방법 각각에 대해 최대 10자리의 정수가 하나씩 대응되는데, 이 수를 “평형정수”라고 하자.
주어진 추 집합을 입력으로 받아서, 생성할 수 있는 모든 평형정수를 증가하는 순서대로 놓았을 때, k번째(0≤k≤1,000,000,000)에 해당되는 평형정수를 출력하는 프로그램을 작성하시오. 특수한 경우로 k=0에 대응되는 평형정수는 0으로, 저울의 양쪽에 아무 추도 놓이지 않은 상태를 말한다. 만일 k번째에 해당하는 평형정수가 없으면 가능한 가장 큰 평형정수를 출력한다.
입력
첫째 줄에는 추 집합의 크기 n이 주어진다. (1≤n≤9) 둘째 줄에는 서로 다른 n개의 추의 무게가 증가하는 순서로 주어진다. 각 수 사이에는 빈 칸이 하나 있다. 셋째 줄에는 여러분이 계산해야 할 평형정수의 순위 k가 주어진다.
2
2 3
1
출력
첫째 줄에 입력에서 주어진 추들로 만들 수 있는 모든 평형정수를 증가하는 순서대로 나열했을 때 k번째가 되는 평형정수를 출력하면 된다. 만일 k번째에 해당되는 평형정수가 없을 경우에는 가능한 가장 큰 평형정수를 출력한다.
3000200
백준 온라인 저지
소스코드
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
static int[] weightArr;
static int n;
static int[] checkSum= {-5,-4,-3,-2,-1,1,2,3,4,5};
static ArrayList<Long> list=new ArrayList<>();
static boolean finish(int[] scale) {
int sum=0;
for(int i=0;i<10;i++) {
sum+=scale[i] * checkSum[i];//평형
}
return (sum==0);
}
static void print(int[] scale) {
String str="";
for(int i=0;i<10;i++) {
str+=scale[i];
}
long result=Long.parseLong(str);
list.add(result);
}
static void DFS(int[] scale,int check,int index) {
if(index==10) {
if(finish(scale))
print(scale);
return;
}
for(int i=0;i<=n;i++) {//weightArr[0]=0;
int weight=weightArr[i];
int using;
if(weight==0)//weight==0이라면 중복체크x
using=0;
else
using=1<<i;
if((using&check)==0) {//안겹치면
scale[index]=weight;
DFS(scale,check+using,index+1);
}
}
}
public static void main(String args[]) {//arraylist에 배열넣으면이상해진다.
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
weightArr=new int[n+1];
for(int i=1;i<=n;i++) {
weightArr[i]=sc.nextInt();
}
int k=sc.nextInt();
int[] scale=new int[10];
DFS(scale,0,0);
if(k>=list.size())
System.out.println(list.get(list.size()-1));
else
System.out.println(list.get(k));
}
}
checkSum으로 가중치를 초기화한다.DFS내에서using와check를 이용해 추의 재사용 여부를 체크하고scale에 추를 놓는다.DFS에 들어가면promising로 가중치를 포함한 무게를 계산한다.
