www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net subset을 사용해서 처리해줬다. 길이가 1이상이라는 조건이 있다 import java.util.Scanner; public class Main { static int n,s; static int[] arr; static int answer; public static void main(String[] args) { Scanner sc=new Scanner(System.in)..
www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net subset으로 집합을 나눈다. vis[번호]=true => a집합, false면 b집합 만약 리스트 두 개를 만들어서 각각 집어넣는다. 리스트 하나라도 길이가 0이다 => 나머지 몰빵 => 집합 2개가 안됨 => return 리스트 두 개의 길이를 합쳤는데 n이 안됨 => 집합이 3개 이상이라는 뜻 => return 그 다음에는 한 집합 내에서 bfs로 인접리스트를 돌리며 한 집합의 모든 원소가 연결되는 지 확인한 후 두 집합 합..
nPr을 먼저해서 n개의 무게추를 순서를 모두 다르게 정렬한 다음 subset으로 왼쪽 혹은 오른쪽(왼쪽의 무게가 더 높도록 제한)으로 넘겨주면서 무게를 계산한다. 가능한 경우의 수를 리턴한다. import java.util.ArrayList; import java.util.Scanner; public class Solution { static int n,t; static int weight[]; static int sum; static int answer; static ArrayList arr=new ArrayList(); public static void main(String[] args) { Scanner sc=new Scanner(System.in); t=sc.nextInt(); for (int ..
import java.util.Scanner; public class Main { static int n,s,b; static int[][] a; static int ans=Integer.MAX_VALUE; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); a=new int[n][2]; for (int i = 0; i Math.abs(sour-bitter) && c!=0) { ans=Math.abs(sour-bitter); } return; } subset(cnt+1,sour*a[cnt][0],bitter+a[cnt][1],c+1); subset(cnt+1,sour,bitter,c); } }
부분 집합으로 풀어주었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Solution { static int t,n,l; static int[] scores; static int[] calories; static int answer; public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in..