-
[백준] 2309번 : 일곱난쟁이 - 자바(JAVA)알고리즘/백준 2022. 5. 4. 00:01728x90
https://www.acmicpc.net/problem/2309
문제 해석
조합 문제로 9C7 == 100을 찾는 문제
정답이 여러 개 존재할 수 있어서 한 개만 출력해야 하는 것과 정렬해주는 것만 주의하면 됩니다.
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main_2309_일곱난쟁이 { static int[] heights = new int[9]; static int[] answers = new int[7]; static boolean flag; public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); for (int i = 0; i < 9; i++) { heights[i] = Integer.parseInt(br.readLine()); } combination(0, 0, 0); } private static void combination(int num, int start, int sum) { // 수식 하나 완성후에는 더이상 탐색x if (flag) { return; } // 100 넘으면 탐색x if (sum > 100) { return; } if (num == 7) { // num==7인경우에만 100을 탐색해야한다. if (sum != 100) { return; } Arrays.sort(answers); StringBuilder sb = new StringBuilder(); for (int e : answers) { sb.append(e + "\n"); } System.out.print(sb.toString()); flag = true; return; } for (int i = start; i < 9; i++) { answers[num] = heights[i]; sum += heights[i]; combination(num + 1, start + 1, sum); sum -= heights[i]; } } }
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 18808번 : 스티커 붙이기 - 자바(JAVA) (0) 2022.05.06 [백준] 19238번 : 스타트 택시 - 자바(JAVA) (0) 2022.05.05 [백준] 10974번 : 모든순열 - 자바(JAVA) (0) 2022.05.04 [백준] 1194번 : 달이 차오른다, 가자. - 자바(Java) (0) 2022.05.03 [백준] 2096번 : 내려가기 - 자바(JAVA) (0) 2022.05.02