[Java] 백준 알고리즘 15649, 15650 번 문제 : N과 M 시리즈 (완전탐색)

--- 1번 문제 ---

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

--- 코드 ---

 

import java.util.LinkedList;
import java.util.Scanner;

public class Bj15649 {
	static boolean[] checked ;
	static LinkedList<Integer> list;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		checked = new boolean[n+1];
		list = new LinkedList<Integer>();
		dfs(n,m);
		sc.close();
	}
	
	public static void dfs(int n, int m) {
		
		// 기저 사례
		if(m==0) {
			for(int i=0; i<list.size(); ++i ) {
				System.out.print(list.get(i)+" ");
			}
			System.out.println();
			return;
		}
		
		
		// 완전 탐색
		for( int i=1; i<=n; ++i ) {
			if(!checked[i]) {
				// 아직 지나가지 않은 상태
				checked[i] = true;
				list.add(i);
				dfs(n,m-1);
				list.removeLast();
				checked[i] = false;
			}
			
		}
		
	}

}

 

 

--- 2번 문제 ---

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

-> 이 문제는 1번 문제에서, 순열이 아닌 조합의 경우를 출력하라는 점이 다르다.

 

--- 코드 ---

 

import java.util.LinkedList;
import java.util.Scanner;

public class Bj15651 {
	static boolean[] checked ;
	static LinkedList<Integer> list;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		checked = new boolean[n+1];
		list = new LinkedList<Integer>();
		dfs(0,n,m);
		sc.close();
	}
	
	public static void dfs(int in , int n, int m) {
		
		// 기저 사례
		if(m==0) {
			for(int i=0; i<list.size(); ++i ) {
				System.out.print(list.get(i)+" ");
			}
			System.out.println();
			return;
		}

		// 완전 탐색
		for( int i=in+1; i<=n; ++i ) {
			if(!checked[i]) {
				// 아직 지나가지 않은 상태
				checked[i] = true;
				list.add(i);
				dfs(i,n,m-1);
				list.removeLast();
				checked[i] = false;
			}
			
		}
		
	}

}

 

탐색 시작 인수인 int in 을 매개변수로 추가해줌으로써, 순열을 조합으로 바꿨다.

 

--- 3번 문제 ---

 

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

-> 2 4 일때, 1 1 이렇게 같은 숫자가 여러개 나와도 된고, 조합의 중복도 인정이 되는 경우 이다.

이 경우에 위에 2번 문제에서 cheked 배열만 제거하면 , 구현은 되는데 시간초과의 문제가 있었다.

이는 list를 사용하는 것의 문제라고 생각하여 StringBuilder 클래스를 이용하여 

이를 구현했고, 이를 통해 문제를 풀 수 있었다.

 

--- 코드 ---

import java.util.Scanner;

public class Bj15651 {
	static boolean[] checked ;
	static StringBuilder s ;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		s = new StringBuilder();
		dfs(n,m);
		sc.close();
	}
	
	public static void dfs( int n, int m) {
		
		// 기저 사례
		if(m==0) {

				System.out.println(s.toString());
			return;
		}

		// 완전 탐색
		for( int i=1; i<=n; ++i ) {
				s.append(i+" ");
				dfs(n,m-1);
				s.delete(s.length()-2, s.length());
		}
		
	}

}

 

--- 4번 문제 ---

 

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

--- 코드 ---

 

import java.util.LinkedList;
import java.util.Scanner;

public class Bj15652 {

	static int[] arr;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		// checked = new boolean[n+1];
		// list = new LinkedList<Integer>();
		arr = new int[m];
		dfs(n, m);
		sc.close();
	}

	public static void dfs(int n, int m) {

		// 기저 사례
		if (m == 0) {
			for (int i = 0; i < arr.length; ++i) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}

		// 완전 탐색
		for (int i = 1; i <= n; ++i) {
			if (arr.length - m > 0) {
				if (arr[arr.length - m - 1] <= i) {
					arr[arr.length - m] = i;
				} else {
					continue;
				}
			}
			else {
				arr[0] = i;
			}
			dfs(n, m - 1);
		}

	}

}

 

 

--- 출처 ---

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

15649번: N과 M (1)

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

15650번: N과 M (2)

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

15651번: N과 M (3)

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

15652번: N과 M (4)