15664 - N과 M 10(백트래킹)

15664 - N과 M 10(백트래킹)

# 주소

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

# 문제

# 문제 해설 및 코드 리뷰

import java.io.*; import java.util.*; public class Main { public static int[] arr,ans; public static int N, M; public static boolean[] visit; public static StringBuilder sb = new StringBuilder(); public static LinkedHashSet set; 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()); arr = new int[M]; ans = new int[N]; set = new LinkedHashSet<>(); st = new StringTokenizer(br.readLine()); visit = new boolean[N]; for(int i = 0; i < N; i++) { ans[i] = Integer.parseInt(st.nextToken()); } Arrays.sort(ans); dfs(0, 0); set.forEach(System.out::println); } public static void dfs(int depth, int t) { if (depth == M) { StringBuilder sb = new StringBuilder(); for (int val : arr) { sb.append(val + " "); } set.add(sb.toString()); sb.append('

'); return; } for(int i = t; i < N; i++) { if(!visit[i]) { visit[i] = true; arr[depth] = ans[i]; dfs(depth+1, i+1); visit[i] = false; } } } }

참 간단한 문제입니다. 정답률 80% 인데는 이유가 있는 것 같습니다. 이전 문제에 이어서 경우의 수를 비내림차순이 되게끔 출력하면 되겠습니다. 따라서 제일 밑의 for문의 i = t부터 시작하여 dfs의 depth와 i랑 각각 +1씩 해주면 계속해서 증가된 원소의 배열값을 얻을 수 있겠습니다.

이전 리뷰에 근본적인 원리가 들어가 있으니 참고해주시길 바랍니다.

https://codingrapper.tistory.com/21

from http://codingrapper.tistory.com/22 by ccl(A) rewrite - 2021-09-25 22:27:50