[백준 2309] 일곱 난쟁이 (C++, Java)

www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

문제풀이

• dfs를 통해 9명 중 7명을 뽑는 Combination(조합)을 해주는 문제
• 조합 코드 : 다시 for문으로 갈때 i=x부터 시작하는것이 중요! visit 중요 !
• sum==100 이면 바로 탈출 dfs 진입 처음 if문에 flag 이용 !

	for(int i = x ; i<9 ; i++)
		{
			if(flag == true)
				break;
			if(vi[i]==false)
			{
				vi[i]=true; 
				//sum = sum + Nan[i];
				dfs(x+1,num+1,sum+Nan[i]);
				
				//sum = sum -Nan[i];
				vi[i]=false;	
			}			
		}

 

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool visit[9] = { false, };
int arrNuan[9] = { 0, };
bool flag = false;
vector<int> v;
void input()
{

	for (int i = 0; i < 9; i++)
	{
		int temp;
		cin >> temp;
		arrNuan[i] = temp;
	}
}
void dfs(int p,int cnt, int sum)
{	
	if (cnt == 7)
	{
		if (sum == 100)
		{
			flag = true;
			sort(v.begin(), v.end());
			for (auto i : v)
			{
				
				cout << i << endl;
			}
		}
		return;
	}

	for (int w = p; w < 9; w++)
	{
		if (!visit[w])
		{
			visit[w] = true;
			v.push_back(arrNuan[w]);
			dfs(w, cnt+1, sum + arrNuan[w]);
			if (flag) break;
			 

			v.pop_back();
			visit[w] = false;
		}

	}
}

int main()
{
	visit[9] = { false, };
	arrNuan[9] = { 0, };
	flag = false;
	for (int i = 0; i < v.size(); i++)
		v.pop_back();
	input();
	dfs(0,0,0);

	return 0;
}

 

Java

package Z_ShinHanCard_Prepare;
import java.util.*;
public class D2백준2309_일곱난쟁이_DFS {

	//9C7 뽑는 경우의 수 !!
	static int[] Nan =  new int[9];;
	static boolean[] vi = new boolean[9];;
	static ArrayList<Integer> arr =new ArrayList<Integer>();
	static boolean flag; 
	static void dfs(int x, int num,int sum)
	{
		
		if(num==7)
		{
			if(sum==100)
			{
				//arr = new ArrayList<Integer>();
				for(int i =0  ; i < 9 ; i++ )
				{
					if (vi[i]==true)
					{
						arr.add(i);
					 
					}
					flag=true;
				 
				}
			}
			return;
		}
		
		for(int i = x ; i<9 ; i++)
		{
			if(flag == true)
				break;
			if(vi[i]==false)
			{
				vi[i]=true; 
				//sum = sum + Nan[i];
				dfs(x+1,num+1,sum+Nan[i]);
				
				//sum = sum -Nan[i];
				vi[i]=false;	
			}			
		}
		
	}
	public static void main(String[] args) 
	{
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		for(int i =0 ; i < 9 ; i ++)
		{
			int temp = sc.nextInt();
			Nan[i] = temp;
		}
		
		dfs(0,0,0);
		
		ArrayList<Integer> answer = new ArrayList<Integer>();
		for(int x : arr)
		{
			answer.add(Nan[x]); 
		}
		Collections.sort(answer);
		
		for(int x : answer)
		{
			System.out.println(x);
		}
		
		
		
	}

}