[백준 / Java] 15652번 N과 M (4)

사용한 알고리즘(백트래킹)

https://cobi-98.tistory.com/22

[필수 알고리즘] 재귀호출 기본 -백트래킹(Backtracking)

 

🔒 15652번 N과 M (4)

✔ 문제 설명

🚩 요구사항 분석

• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다. == 중복도 허용
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
  •  

🔑 문제풀이

자연수 N과 M을 정의하기위해 BufferedReader을 사용하여 StringTokenizer로 값을 전역변수 지정하였다.

 

N과 M (1)의 경우처럼 depth를 통해 재귀가 깊어질 때마다 (DMBackTracking함수) depth를 1씩 증가시키는 것은 같다.

하지만 중복을 허용하기에 현재 값을 확인해줄 변수인 numberCheck를 받으면 비 내림차순(중복의 값)을 표현할 수 있게 된다.

 

depth를 통해 재귀가 깊어질 때마다 (DMBackTracking함수) depth를 1씩 증가시켜

M과 같아지면 더 이상 재귀를 호출하지 않고 탐색과정 중 값을 담았던 arr 배열을 출력해 주고 return 해준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static int N;
    public static int M;
    public static int [] arr;
    public static StringBuilder sb = new StringBuilder();

    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];

        NMBacktracking4(1,0);
        System.out.println(sb);
    }

    public static void NMBacktracking4(int sort,int depth){
        if(depth == M){
            for (int value : arr) {
                sb.append(value).append(' ');
            }
            sb.append('\n');
            return;
        }

        for (int i = sort; i <= N; i++) {
            arr[depth] = i;
            NMBacktracking4(i,depth+1);
        }
    }
}