15651 - N과 M 3(백트래킹)

15651 - N과 M 3(백트래킹)

# 주소

www.acmicpc.net/problem/15651

# 문제

# 문제 분석

이번에도 백트래킹을 이용하여 문제를 해결해야 합니다. 이번엔 저번 문제처럼 간단히 해결할 수 있습니다.

다만 중복을 허용하여 경우의 수를 따지는 것이므로 코드를 작성할 때 arr의 값은 i로 통일하되 arr[depth +1]만 해주어

이전 문제와 마찬가지로 depth == M일 때에만 출력하고 return 하는 방식을 취했습니다.

따라서 dfs함수를 작성하는 방식에 있어서 인수를 이전 문제들과 달리 depth 한 개만 받으면 된다는 차이점이 있습니다.

그리고 Scanner, Print 방식을 사용하면 시간 초과가 뜨므로 이번에는 StringBuilder 방법으로 문제를 풀었습니다.

다음에는 이것보다 메모리 시간을 더 단축시킬 수 있는 StringBuffered 방식으로 풀이하겠습니다.

# 코드 해설

import java.util.Scanner; public class Main { public static int[] arr; public static int N, M; public static StringBuilder sb = new StringBuilder(); public static void main(String[] args) { Scanner in = new Scanner(System.in); N = in.nextInt(); M = in.nextInt(); arr = new int[M]; dfs(0); System.out.print(sb); } public static void dfs(int depth) { if (depth == M) { for (int val : arr) { sb.append(val + " "); } sb.append('

'); return; } for (int i = 1; i <= N; i++) { arr[depth] = i; dfs(depth + 1); } } }

from http://codingrapper.tistory.com/15 by ccl(A) rewrite - 2021-09-24 02:27:46