알고리즘 공부 #8 : 완전탐색 3(n과m)

백준 15654 : n과 m (5)

처음엔 조합으로 했다가 조합으로는 7 1 같이 순서가 반전된게 나올수 없다고 깨달았다 ..ㅠㅠ 애초에 순열로 풀어야되는걸 깨달았다. 그래서 비트마스크를 이용하여 풀었다

import java.util.*;

public class Main {
	public static Scanner scan =new Scanner(System.in);
	public static StringBuilder sb=new StringBuilder();
	static int n,m;
	static int cnt=0,tmp2=0;
	static int arr[];
	static int tmp[];
	static int flag;
	public static void main(String[] args) {
			n=scan.nextInt();
			m=scan.nextInt();
			arr=new int[n];
			tmp=new int[m];
			for(int a=0;a<n;a++) {	
				arr[a]=scan.nextInt();
				}
			Arrays.sort(arr);
			solve(0,0);
			System.out.print(sb);
		}

	public static void solve(int cnt,int used) {	//n개의 자연수 중 m개를 고른 수열

		if(cnt==m) {
			for(int i=0;i<m;i++) {
				sb.append(tmp[i]+" ");				
				
			}
			sb.append("\n");
			return;
		}
		for(int i=0;i<n;i++) {
			if((used&1<<i)!=0) {//i번째 원소가 사용됐으면
				continue;
			}
			tmp[cnt]=arr[i];		//사용되지 않았으면 tmp에 저장 
			solve(cnt+1,used|1<<i);
		}
		
	}
}

백준 15655 : n과 m(6)

아까 위에 문제 풀다가 나온게 이문제 답이였다 ^^..

import java.util.*;

public class Main {
	public static Scanner scan =new Scanner(System.in);
	public static StringBuilder sb=new StringBuilder();
	static int n,m;
	static int cnt=0,tmp2=0;
	static int arr[];
	static int tmp[];
	static int flag;
	public static void main(String[] args) {
			n=scan.nextInt();
			m=scan.nextInt();
			arr=new int[n];
			tmp=new int[n];

			for(int a=0;a<n;a++) {	
				arr[a]=scan.nextInt();
				}
			Arrays.sort(arr);
			solve(0,0,false);
			System.out.print(sb);
		}

	public static void solve(int pos,int choice,boolean flag) {	//n개의 자연수 중 m개를 고른 수열
		if(pos>n) {
			return;
		}
		
		if(flag==true) {
			tmp[pos-1]=1;
		}
		if(flag==false&&pos!=0) {
			tmp[pos-1]=0;
		}
		if(choice==m) {
			for(int i=0;i<n;i++) {
				if(tmp[i]==1) {
					sb.append(arr[i]+" ");
				}
			}
			sb.append("\n");
			return;
		}
		
		
		solve(pos+1,choice+1,true);
		solve(pos+1,choice,false);
		return;
	}
}

백준 15656 : n과 m(7)

5번문제에서 used를 체크하지않고 그냥 반복하면 되는 문제이다.

import java.util.*;

public class Main {
	public static Scanner scan =new Scanner(System.in);
	public static StringBuilder sb=new StringBuilder();
	static int n,m;
	static int cnt=0,tmp2=0;
	static int arr[];
	static int tmp[];
	static int flag;
	public static void main(String[] args) {
			n=scan.nextInt();
			m=scan.nextInt();
			arr=new int[n];
			tmp=new int[m];
			for(int a=0;a<n;a++) {	
				arr[a]=scan.nextInt();
				}
			Arrays.sort(arr);
			solve(0);
			System.out.print(sb);
		}

	public static void solve(int cnt) {	//n개의 자연수 중 m개를 고른 수열

		if(cnt==m) {
			for(int i=0;i<m;i++) {
				sb.append(tmp[i]+" ");				
				
			}
			sb.append("\n");
			return;
		}
		for(int i=0;i<n;i++) {

			tmp[cnt]=arr[i];		//사용되지 않았으면 tmp에 저장 
			solve(cnt+1);
		}
		
	}
}

백준 15657 : n과 m (8)

이전 문제와 비슷하고 for문 시작하는 부분이 이전 재귀에서 pos부터 시작하면 된다!

import java.util.*;

public class Main {
	public static Scanner scan =new Scanner(System.in);
	public static StringBuilder sb=new StringBuilder();
	static int n,m;
	static int cnt=0,tmp2=0;
	static int arr[];
	static int tmp[];
	static int flag;
	public static void main(String[] args) {
			n=scan.nextInt();
			m=scan.nextInt();
			arr=new int[n];
			tmp=new int[m];
			for(int a=0;a<n;a++) {	
				arr[a]=scan.nextInt();
				}
			Arrays.sort(arr);
			solve(0,0);
			System.out.print(sb);
		}

	public static void solve(int cnt,int pos) {	//n개의 자연수 중 m개를 고른 수열

		if(cnt==m) {
			for(int i=0;i<m;i+=1) {
				sb.append(tmp[i]+" ");				
			}
			sb.append("\n");
			return;
		}
		for(int i=pos;i<n;i++) {

			tmp[cnt]=arr[i];		//사용되지 않았으면 tmp에 저장 
			solve(cnt+1,i);
		}
		
	}
}