[백준] 15652번: N과 M (4) (dfs, 중복포함, 비내림차순)

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

15652번: N과 M (4)

코드

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

public class Main {
	public static int arr[];
	public static int N;
	public static int M;
	public static StringBuilder sb = new StringBuilder();
	
	public static void dfs(int count) {
		if(count == M) {
			for(int i=0; i<M-1; i++) {
				if(arr[i] > arr[i+1])
					return;
			}
			
			for(int i : arr) 
				sb.append(i + " ");
			sb.append("\n");
			return;
		}
		
		for(int i=1; i<=N; i++) {
			arr[count] = i;
			dfs(count+1);
		}
		
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String str = bf.readLine();
		StringTokenizer st = new StringTokenizer(str);
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[M];
		dfs(0);
		
		System.out.println(sb);
		bf.close();
	}

}

풀이

N과 M(2) + N과 M(3) 두 문제를 섞어 만든 문제이다.

중복허용 + 비내림차순

중복허용 -> 방문체크 X, 같은 곳 탐색할 수 있다.

비내림차순 -> arr[i] > arr[i+1] 이 참일때, return; 을 통해 재귀호출한 dfs()메소드를 종료한다.

 

N과 M(1)

N과 M(2)

N과 M(3)