[알고리즘] 백준 15656 N과 M (7) -백트래킹- 자바

[알고리즘] 백준 15656 N과 M (7) -백트래킹- 자바

300x250

SMALL

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

오랜만에 알고리즘을 풀고 백트래킹의 기본이라 할 수 있는 N과 M 시리즈를 풀어봤습니다.

확실히 오랜만에 자바를 사용하고 알고리즘을 풀었더니 없던 실력도 많이 줄은 것 같네요.. ㅠ

주어진 숫자를 여러번 사용할 수 있지만 오름차순으로 중복되지 않은 순열을 출력해야 했습니다.

그러므로 isVisited[] 같은 중복을 체크하는 Boolean 형 타입은 필요하지 않고 StringBuilder와 순열을 저장할 배열만을 사용했습니다. 추가로 오름차순으로 출력해야하므로 정렬을 하는 전처리도 진행하였습니다.

풀이는 다음과 같습니다.

[Java]

import java.util.Arrays; import java.util.Scanner; public class Main { private static int N; private static int M; private static int[] nums; private static StringBuilder sb = new StringBuilder(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); M = sc.nextInt(); nums = new int[N]; for (int i = 0; i < N; i++) { nums[i] = sc.nextInt(); } Arrays.sort(nums); dfs(0, new int[M]); System.out.println(sb.toString()); } private static void dfs(int depth, int[] answers) { if (depth == M) { for (int i = 0; i < M; i++) { sb.append(answers[i]).append(" "); } sb.append("

"); return; } for (int i = 0; i < N; i++) { answers[depth] = nums[i]; dfs(depth + 1, answers); } } }

https://github.com/mtjin/algorithm_practice/commit/8e764158039d010159aef2bb64e6ed1499e4d802

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!

300x250

LIST

from http://youngest-programming.tistory.com/643 by ccl(S) rewrite - 2021-11-23 05:01:56