백준_15652 N과 M(4) (자바) / 백트래킹

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Back_15652 {
	
	static int N,M;
	static int[] arr;
	static StringBuilder sb;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		sb = new StringBuilder();
		arr = new int[M];
		
		perm(0,0);
		System.out.println(sb);
	}
	private static void perm(int dep,int val) {
		if(dep == M) {
			for (int i = 0; i < arr.length; i++) {
				sb.append(arr[i]+" ");
			}
			sb.append("\n");
			return;
		}
		for (int i = 1; i <=N ; i++) {
			if(val>i) {
				continue;
			}
			arr[dep]=i;
			perm(dep+1,i);
		}
	}
}

 

※ 내 생각

이 문제는 백트래킹 및 dfs를 활용하는 문제입니다.

perm을 통해서 배열에 값을 담고 재귀를 통해서 진행해 줍니다.
dep가 원하는 위치가 되면 종료 조건을 만들어 주고 출력을 해주면 됩니다.