[백준_15650번] N과 M (2)

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

15650번: N과 M (2)

[문제]

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

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

 

[입력 조건]

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

 

[코드]

import java.util.Scanner;

public class BaekJoon_15650 {
	static int n,m;
	static int[] arr;
	static StringBuilder sb=new StringBuilder();
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		
		arr=new int[m+1];
		dfs(1,0);
		System.out.println(sb);
	}
	
	// 출력 시작 값과 깊이 값을 매개변수로 하는 dfs 함수
	static void dfs(int start, int depth) {
		// 깊이가 m과 같아지면 배열에 저장된 값들 한번에 출력
		if(m==depth) {
			for(int i=0;i<m;i++) sb.append(arr[i]+" ");
			sb.append("\n");
			return;
		}
		/*
		 * 해당 문제는 n=4, m=2인 경우
		 * (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) 와 같이
		 * 시작 값의 이후 값들만 출력해야 한다. 따라서 시작 지점과 깊이를 매개변수로 하여
		 * 시작 이전의 값들을 출력하지 않게 구성해야 한다.
		 */
		for(int i=start;i<=n;i++) {
			arr[depth]=i;
			dfs(i+1,depth+1);
		}
	}
}

 

[고찰]

 이번 문제는 앞선 문제와 출력 형식만 다른 문제이다. 출력 형태가 다름에 따라 함수의 매개변수만 다르게 해주어 출력하면 쉽게 해결 할 수 있는 문제였다. 아직 백트래킹, DFS에 미숙하기 때문에 여러번 생각하게 하는 문제였다.