[코테]05-브루트 포스(N과 M)

• 재귀함수
  1) 순서
  N가지를 M개 뽑을건데 각서와 관련되어 있는 문제.
  N!의 시간복잡도를 가짐
  N가지가 있으면 다 할 수는 있지만 M개를 어떤 순서로 할 것인지를 고르는 것.
  2) 선택
  N가지가 있을 때 선택과 관련되어 있음
  2^n의 시간복잡도를 가짐

N과M(1)

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제
1<=M<=N<=8

• 재귀 : 어떤 위치에 올 수 있는 수를 결정.
  -> 위치만 변하고 할 수 있는 방법은 같은 방법이기 때문에 재귀함수를 사용함.

• 1~N까지의 숫자중에 하나 / 1~N까지 숫자중 하나 ...... / M번째 까지 반복

• 1부터 N까지의 수 중에서 앞에서 사용하지 않은 수

• 위치 : 함수의 인자. (첫 번째, 두 번째 등등 그 위치가 중요함)

• 앞에서 사용한 수도 관리해주어야함.

  
  <풀이>

• c[i] : i를 사용했으면 true, 사용하지 않았으면 false

• a[10] : 수열을 저장.

• go(index,n,m) : index번째의 수를 결정

• 1부터 n중에서 사용하지 않은 수를 찾음.

• 재귀함수에서 가장 중요한 것은 함수를 호출하기 전에 함수의 호출을 미리 준비해야함.

import java.util.Scanner;

public class Main {
		static boolean c[] = new boolean[10];
		static int a[]=new int[10];
		
		static void go(int index,int n,int m) {
			if(index==m) {
				//index가 m이랑 같아지면 
				for(int i=0;i<m;i++) {
					System.out.print(a[i]);
					if(i != m-1)
						System.out.print(' ');
				}
				System.out.println();
				return;
				//끝
			}
			for(int i=1;i<=n;i++) {
				if(c[i])	//이미 해당 숫자가 쓰였으면 continue;
					continue;
				//해당 숫자 사용했다고 true로 바꿔주기
				c[i] = true;
				a[index] = i;
				go(index+1,n,m);
				
				c[i]=false; //다시 사용한 것을 FALSE로 만들어 주어야함
                //함수의 호출 미리 준비.
			}
				
		}
		public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			int n= sc.nextInt();
			int m = sc.nextInt();
			go(0,n,m);
			
		}		
	}

백준 선생님이 알려준대로 풀었는데 시간초과가 나네,,왜 이것만 나지ㅠ왜 이것만 나지ㅠ

N과 M(2)

1부터 N까지 자연수 중에서 중복없이 M개를 고른 수열을 모두 구하는 문제(오름차순)
1<=M<=N<=8
N과M(1)과 유사하지만 오름차순이라는 것만 다름.
각각의 자연수를 선택하는 경우와 선택하지 않는 경우가 있다.

• start를 추가해주면 됨.
• index번째에 올 수 있는 수는 start부터 n까지이다.
• index에 i가 왔다면 index+1은 i+1부터 n까지 올 수 있음.
• c[i] -> 사용했으면 true, 아니면 false
• 절대 중복된 수를 사용하지 않아서 상관없음.
• 순서 x , 선택의 관점에서 보는 것.
• 선택한 수의 개수도 기록해주어야함.
• index : 수 index를 의미
• selected : 선택한 수의 개수
  -> 수 index를 선택할 것인지 선택하지 않을 것인지를 결정해야함.

  import java.util.Scanner;

public class Main {
static boolean c[] = new boolean[10];
static int a[]=new int[10];

	static void go(int index,int start,int n,int m) {
		if(index==m) {
			for(int i=0;i<m;i++) {
				System.out.print(a[i]);
				if(i != m-1)
					System.out.print(' ');
			}
			System.out.println();
			return;
		}
		for(int i=start;i<=n;i++) {
			c[i] = true;
			a[index] = i;
			go(index+1,i+1,n,m);
			c[i]=false;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		int m = sc.nextInt();
		go(0,1,n,m);
	}		
}

N과 M(3)

1부터 N까지 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복 선택 가능)
1<=M<=N<=7
중복선택 없애는 것만 제거해주면 됨.

import java.util.Scanner;

public class Main {
		static boolean c[] = new boolean[10];
		static int a[]=new int[10];
		
		static void go(int index,int n,int m) {
			if(index==m) {
				for(int i=0;i<m;i++) {
					System.out.print(a[i]);
					if(i != m-1)
						System.out.print(' ');
				}
				System.out.println();
				return;
			}
			for(int i=1;i<=n;i++) {
				c[i] = true;
				a[index] = i;
				go(index+1,n,m);
				c[i]=false;
			}
		}
		public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			int n= sc.nextInt();
			int m = sc.nextInt();
			go(0,n,m);
		}		
	}

~~이것도 시간초과,,, ~~

N과 M(4)

1부터 N까지 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복 선택 가능,비내림차순)
1<=M<=N<=8

• N과 M(2)에서는 오름차순 start를 넣어줬고, N과 M(3)에서는 사용여부기록 X
• 여기서는 start~n이 i라면 i+1이 아니라 i+1부터~n까지 가능(중복이 가능하기 때문에)

import java.util.Scanner;

public class Main {
		static boolean c[] = new boolean[10];
		static int a[]=new int[10];
		
		static void go(int index,int start,int n,int m) {
			if(index==m) {
				for(int i=0;i<m;i++) {
					System.out.print(a[i]);
					if(i != m-1)
						System.out.print(' ');
				}
				System.out.println();
				return;
			}
			for(int i=start;i<=n;i++) {
				c[i] = true;
				a[index] = i;
				go(index+1,i,n,m);
				c[i]=false;
			}
		}
		public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			int n= sc.nextInt();
			int m = sc.nextInt();
			go(0,1,n,m);
		}		
	}

N과 M(5)

import java.util.Arrays;
import java.util.Scanner;

public class Main {
		static boolean c[] = new boolean[10];
		static int a[]=new int[10];
		static int num[] = new int[10];
		
		static StringBuilder go(int index,int n,int m) {
			if(index==m) {
				StringBuilder sb = new StringBuilder();
				for(int i=0;i<m;i++) {
					sb.append(num[a[i]]);
					if(i != m-1)
						sb.append(" ");
				}
				sb.append("\n");
				return sb;
			}
			StringBuilder res = new StringBuilder();
			for(int i=0;i<n;i++) {
				if(c[i])	
					continue;
				c[i] = true;
				a[index] = i;
				
				res.append(go(index+1,n,m));
				c[i]=false;
			}
			return res;
		}
		public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			int n= sc.nextInt();
			int m = sc.nextInt();
			for (int i=0;i<n;i++) {
				num[i]=sc.nextInt();
			}
			Arrays.sort(num,0,n);
			System.out.println(go(0,n,m));
		}		
	}