2309번: 일곱 난쟁이
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
www.acmicpc.net
접근법
[백준 일곱 난쟁이 2309] 는 브루트 포스 기법을 이용해서 푸는 스페셜저지 문제이다. 스페셜저지 문제는 문제의 정답이 여러 가지일 때 유저가 출력한 답이 맞는지 안 맞는지 확인하는 문제이다. 이 문제에서는 9명의 키가 주어진다. 그리고 9명의 키 중에 7개를 골라서 합이 100이 되는 7명을 찾고 그 7명의 키를 오름차순으로 출력해주면 된다.
답이 여러개가 존재할 수도 있어 한 번 일곱 난쟁이가 정해지고 출력을 해주면 flag 변수로 답이 한 번만 출력되고 더이상 탐색(출력)되지 않도록 해야한다.
9명중 7명을 뽑는 조합 ! (무작위로 뽑기 때문에 순서가 상관 없음) 을 사용해야한다. 이 문제는 조합의 기본 문제로 9C2 = 9C7과 같다. 9명의 난쟁이 중에서 7명의 난쟁이를 선택하는 것은 다른 말로 9명의 난쟁이 중 포함되지 않는 2명의 난쟁이를 찾으면 된다. (순서 상관 없음)
9명중 2명을 뽑는 조합 ! (무작위로 뽑기 때문에 순서가 상관 없음) => 이중 for문으로 브루트 포스 알고리즘 (완전 탐색)
9명 중 7명을 선택 == 9명 중 2명을 제외 따라서 제외할 2명의 조합을 모두 탐색하면서 조건에 맞는 지 확인한다.
성능 요약
메모리: 14160 KB, 시간: 120 ms
분류 : 브루트포스 알고리즘(bruteforcing), 정렬(sorting)
전체 코드 (JAVA)
import java.util.*;
import java.io.*;
public class BOJ_B1_2309_일곱난쟁이 {
static int sum =0;
static int[] arr;
static boolean flag;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
arr = new int[9];
for (int i = 0; i < 9; i++) {
arr[i] = Integer.parseInt(br.readLine());
sum += arr[i]; // 난쟁이 9명의 키의 합
}
// 순차 정렬
Arrays.sort(arr);
for (int i = 0; i < arr.length; i++) { //브루트 포스
for (int j = 0; j < arr.length; j++) {
// dfs는 flag로 백트레킹, 난쟁이 키는 다 달라서 인덱스가 겹칠 수 없음
if(!flag &&i!=j) comb(i, j);
}
}
}
private static void comb(int idx1, int idx2) {
int count = arr[idx1] + arr[idx2];
StringBuilder st = new StringBuilder();
if(sum-count==100) {
for(int person : arr) {
if(person!=arr[idx1] && person!=arr[idx2]) st.append(person).append("\n");
}
System.out.print(st);
flag = true;
}
}
}
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] high = new int[9];
int sum = 0;
int spyA = 0, spyB = 0;
for (int i = 0; i < high.length; i++) { // 난쟁이 키 입력
high[i] = sc.nextInt();
sum += high[i]; // sum은 난쟁이 9명의 키의 합
}
Arrays.sort(high); //키를 오름순서로 정렬
for(int a = 0; a < high.length-1; a++) { //브루트 포스
for(int b = a+1; b < high.length; b++) {
if(sum - high[a] - high[b] == 100) { //핵심
spyA = a;
spyB = b;
break;
}
}
}
for(int j = 0; j < high.length; j++) { // 진짜 난쟁이 키 출력
if(j == spyA || j == spyB) //주의
continue;
System.out.println(high[j]);
}
sc.close();
}
}
조합 코드 (1)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int[] dwarf = new int[9]; // 입력받을 아홉 난쟁이
static int[] seven = new int[7]; // 임시로 저장할 일곱 난쟁이
static int[] answer = new int[7]; // 답이 될 일곱 난쟁이
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for (int i = 0; i < 9; i++) {
dwarf[i] = sc.nextInt();
}
Arrays.sort(dwarf); // 입력받은 아홉 난쟁이 정렬
combination(0, 0, 0); // 조합
for (int a : answer) { // 답 출력
System.out.println(a);
}
}
private static void combination(int cnt, int start, int sum) {
if (cnt == 7) {
if (sum == 100) { // 합이 100일 때 답에 해당 일곱 난쟁이를 저장
for (int i = 0; i < 7; i++) {
answer[i] = seven[i];
}
}
return;
}
for (int i = start; i < 9; i++) {
seven[cnt] = dwarf[i];
combination(cnt + 1, i + 1, sum + dwarf[i]);
}
}
}
조합 코드 (2)
import java.io.InputStreamReader;
import java.util.Arrays;
import java.io.BufferedReader;
import java.io.IOException;
public class BOJ2309 {
static int N = 9, K = 100;
static int child[] = new int[N];
static int realChild[] = new int[7];
static boolean ckEnd = false;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 난쟁이들의 키 입력
for (int i = 0; i < N; i++)
child[i] = Integer.parseInt(br.readLine());
process(0, 0, 0);
}
/**
* 일곱 난쟁이를 뽑을 수 있는 모든 경우의 수
* @param idx 난쟁이의 위치
* @param cnt 뽑은 난쟁이의 수
* @param sum 뽑힌 난쟁이들 키의 합
*/
public static void process(int idx, int cnt, int sum) {
// 키의 합이 100인 일곱 난쟁이가 다 뽑힌 상태면
// 더이상 경우의 수를 확인할 필요가 없으므로 return
if(ckEnd) return;
// 일곱 난쟁이가 뽑히면
if(cnt == 7) {
// 뽑힌 난쟁이들의 키의 합이 100이 되는지 확인
if(sum == K) {
// 키의 합이 100이라면 난쟁이들의 키를 오름차순으로 정렬 후 출력
Arrays.sort(realChild);
for (int i = 0; i < 7; i++)
System.out.println(realChild[i]);
ckEnd = true;
}
return;
}
if(idx >= N) return;
// 일곱 난쟁이가 뽑히기도 전에 키의 합이 100을 초과하면 return
if(sum > K) return;
// 이 난쟁이가 진짜? 한번 뽑아볼까?
realChild[cnt] = child[idx];
process(idx + 1, cnt + 1, sum + child[idx]);
// 이 난쟁이는 안 뽑고 넘어갈래
process(idx + 1, cnt, sum);
}
}서로 다른 난쟁이를 for문으로 표현
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] arr = new int[9];
int sum = 0;
for (int i = 0; i < 9; i++) {
arr[i] = Integer.parseInt(br.readLine());
sum += arr[i];
}
for (int i = 0; i < 8; i++) {
for (int j = i+1; j < 9; j++) {
if (sum - arr[i] - arr[j] == 100) {
arr[i] = 0;
arr[j] = 0;
Arrays.sort(arr);
for (int k = 2; k < 9; k++) {
System.out.println(arr[k]);
}
return;
}
}
}
}
}코드 리뷰
가짜 난쟁이의 값을 제외시킬 때 나는 두 쌍의 난쟁이가 아니면 StringBuilder에 넣었는데 다른 분 중에 continue를 써서 제외시킨(건너띄다) 경우도 있었다.
