Baekjoon15649: N과 M(1)

N과 M (1)

 

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

1 초

512 MB

45383

27724

18525

60.385%

문제

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

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

입력

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

출력

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

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

풀이

M에 따라서 반복문의 수가 달라지기 때문에 재귀없이 반복문으로 풀이하기 매우 어려워보인다. 백트래킹의 개념을 참고한 메소드 재귀 호출로 풀이할 수 있었다.

메소드 내 반복문 안에서 재귀 호출을 시행한다면 현 순간 한바퀴 돌고 있는 반복문 단락이 마치기 전까지 재귀가 연속적으로 호출된다.

깊이에 따라 배열 index 도 증가하며 값을 저장하고 특정 깊이에 도달하면 배열의 값을 출력하도록 한다

import java.io.*;
import java.util.*;
public class Main {
	static boolean[] arr;
	static int[] record;
	static void sequence(int N, int M, int Depth) {
    
		if(Depth==M) {
			for(int i=0; i<M; i++) {
					System.out.print(record[i]+" "); //그 동안의 배열의 값을 출력
			}
			System.out.print("\n");
			return; //출력 후 뒤 반복문이 실행되지 않도록 종료한다
		}
		
		for(int i=1; i<N+1; i++) {
			if(arr[i]==false) { //재귀 호출을 생각해 이미 기록된 값은 사용하지 않는다
				arr[i]=true; //사용하는 즉시 기록해주고
				record[Depth]=i; //그 값을 배열에 입력한 뒤
				sequence(N,M,Depth+1); //재귀호출을 한다
				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); //메소드만 실행하면 알아서 출력된다
		
 }}