[조합] 백설공주와 일곱 난쟁이(백준 3040번, 자바)

3040번: 백설 공주와 일곱 난쟁이 (acmicpc.net)

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

 

Next Permutation 코드 구현 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_3040{

	static int N=9;
	static int R=2;
	static int[] num;
	static int[] p;
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	
		
		num=new int[9];
		p=new int[9];
		
		
		int sum=0;
		for(int i=0;i<N;i++) {
			num[i]=Integer.parseInt(br.readLine());
			sum+=num[i];
		}
	
		
		//flag 역할의 배열의 전처리 
		int cnt=0;

		while(++cnt<=R) { //R개만큼 뒤에서 0이 아닌 값으로 채운다. 
			p[N-cnt]=1;
		}
		do {
			int sum2=0;
			for(int i=0;i<N;i++) {
				if(p[i]!=0)sum2+=num[i];
			}
			if(sum2==sum-100) break;
		}while(np(p));
		
		for(int i=0;i<N;i++) {
			if(p[i]==0) System.out.println(num[i]);
		}
	}
	
	private static boolean np(int[] p) {
		
		int n=p.length;

		//1. 뒤쪽부터 꼭대기를 찾는다. 
		int i=n-1; 
		
		while(i>0 && p[i-1]>=p[i]) --i;
		
		if(i==0) return false;//현재 만들 수 있는 가장 큰 순열 
		
		//2. 
		int j=n-1;
		while(p[i-1]>=p[j]) --j;
		

		//3. 꼭대기 바로 앞(i-1)자리와 그 자리값보다 한 단계 큰 자리(j)수와 교환 
		swap(p,i-1,j);
		
	//4. 꼭대기부터 맨 뒤까지 오름차순으로 정렬
		int k=n-1;
		while(i<k) {
			swap(p,i++,k--);
		}
		
		return true;
	}
	
//스와핑 코드 
	private static void swap(int[] input, int i, int j) {
		int temp=input[i];
		input[i]=input[j];
		input[j]=temp;
	}
	
}