[알고리즘] 백준 15652 N과 M (4)

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 BOJ_15642 {
    static int n;
    static int m;
    static int[] arr;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[m];
        visited = new boolean[n + 1];

        backTracking(0);
        System.out.println(sb);
    }

    static void backTracking(int depth) {
        if (m == depth) {
            for (int i = 0; i < arr.length; i++) {
                sb.append(arr[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        for (int i = 1; i < n + 1; i++) {
            if (depth == 0 || (arr[depth - 1] <= i)) {
                arr[depth] = i;
                backTracking(depth + 1);
            }
        }
    }
}

 

다른 N과 M 문제와 마찬가지로 백트래킹 문제이다.

 

문제 조건은 한 수열 내에서는 반복되는 숫자가 나올 수 있으나 중복되는 수열을 여러번 출력하면 안된다.

 

또한 비내림차순이여야한다.

 

한 수열 내에서 반복적인 숫자가 나올 수 있으므로 visited[]는 필요가 없어진다.

 

또한 if (depth == 0 || (arr[depth - 1] <= i)) 문을 통해서 depth가 0이거나

 

arr[depth - 1] 보다 i가 작거나 같을 때만 재귀함수를 타도록 구현하여 문제를 해결하였다.

 

depth가 0일때 if문이 에러가 날 수도 있다고 생각할 수 있는데, or은 맨 왼쪽이 맞으면 뒤에 조건은 패스되기에 오류가 안난다.