[Baekjoon] 백준 3040 백설 공주와 일곱 난쟁이 (B2, 조합) - Java

링크

https://www.acmicpc.net/problem/3040

3040번: 백설 공주와 일곱 난쟁이

 

 

 

문제 해석

9개의 숫자가 입력으로 들어올 때,

9개의 숫자 중 7개의 숫자 합이 정확히 100이 되도록하는 7개의 수를 찾아라 

 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int[] arr = new int[9];
		
		for (int i = 0; i < arr.length; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		recursive(arr,new int[7], 0, 0);
	}

	private static void recursive(int[] arr, int[] sel, int aIdx, int sIdx) {
		// basis part
		if (sel.length == sIdx) {
			int sum = 0;
			for (int i = 0; i < sel.length; i++) {
				sum = sum + sel[i];
			}
			if (sum == 100) {
				for (int i = 0; i < sel.length; i++) {
					System.out.println(sel[i]);
				}
			}
			return;
		}
		
		// inductive part
		for (int i = aIdx; i < arr.length; i++) {
			
			sel[sIdx] = arr[i];
			recursive(arr, sel, i + 1, sIdx + 1);
		}
	}
}

 

 

 

코드 해석

순서를 상관하지 않으며, 중복인 수를 허용하지 않는 숫자 배열을 찾는 문제이므로 조합으로 문제를 해결해야 합니다.

 

7개의 숫자를 찾은 후 더한 값이 100이 되는지 여부를 확인하여 100이라면 각 수를 출력하면 되는 단순한 조합 문제입니다.

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice