[백준] 15651번: N과 M (3) (dfs, 중복포함)

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

15651번: N과 M (3)

코드

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 : 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 시리즈 3번째문제. 

수를 뽑되 같은 수를 여러 번 골라도 된다. - 중복 허용하는 문제다.

따라서 이전의 문제는 1을 탐색하고, 방문했을경우 2를탐색하는 식으로 dfs를 돌렸으나,

이 문제는 1을 탐색하고 다시 1을 탐색한다.(count가 주어진 M과 같을때까지) - 완전탐색.

 

* 이 문제에서 Scanner와 기본적인 출력을 할 경우 시간초과가 발생하는데,

StringBuilder + BufferedReader 클래스를 활용해 시간 초과가 발생하지 않았다.

 

N과 M(1)

N과 M(2)