Baekjoon15650: N과 M(2)

N과 M (2)

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

30507

22946

16718

74.714%

문제

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

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

입력

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

출력

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

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

 

풀이

순열을 떠올릴 수 있는 문제다.

예제 2을 참고하면, 다음을 반복한다

1을 선택한 후 1보다 큰 숫자를 다시 선택

2를 선택한 후 2보다 큰 숫자를 다시 선택

3을 선택한 후 3보다 큰 숫자를 다시 선택

*4는 4보다 큰 숫자가 없으므로 시행하지 않음

이 조건을 추가해 재귀호출을 할 때 현재 선택한 숫자보다 큰 숫자를 선택하도록 만들면 될 것이다.

import java.io.*;
import java.util.*;
public class Main {
	static boolean[] arr;
	static int[] record;
	static void sequence(int N, int M, int Depth, int Select) { //통제하기위해 새로운 변수를 추가
		if(Depth==M) {
			for(int i=0; i<M; i++) {
					System.out.print(record[i]+" ");
			}
			System.out.print("\n");
			return;
		}
		
		for(int i=Select; i<N+1; i++) {
			if(arr[i]==false) {
				arr[i]=true;
				record[Depth]=i;
				sequence(N,M,Depth+1,i+1); //현재 i보다 큰 값을 선택하도록 강요한다
				arr[i]=false;
			}
		}
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		arr = new boolean[N+1]; //수가 중복되는 것을 방지하기 위한 논리배열
		record = new int[M];
		
		sequence(N,M,0, 1);
		
 }}