[ 백준 15650번 문제 ] N과 M (2) - JAVA

 

이번에는 백준 15650번 문제를 통해 백트래킹 알고리즘 학습을 강화해 보자.
저번 15649번 문제에서 살짝 변형된 문제이다.

문제 핵심

• 1부터 N까지의 자연수 중 중복 없이 M개를 고른 수열
• 1 <= M <= N < 8
• 오름차순이여야 한다.

풀이 과정

저번에는 모든과정을 체크했다면 이번 문제는 앞에 숫자가 커짐에 따라 끝의 숫자의 개수가 작아지므로 ( 즉, 오름차순이므로 ) 앞에 숫자 기준으로만 생각하면 된다. 다음 그림과 같이 진행된다. N = 4, M = 2 기준

 

1. 배열 첫 번째 요소를 채워 넣는다. 

2. 두번 째 요소를 넣기 위해 다시 함수를 호출하여 1-1로 진행한다.

3. 두번 째 요소를 넣은 후 다시 함수를 호출하고 깊이와 M값이 같기 때문에 출력한 후 반환한다.

4. 1-1 안에 배열에서 i 값이 증가한 1-2 와 같이 진행되어 이를 N값 전까지 반복한다.

 

private static void backTracking(int depth, int M, int N, int start) {
    if (depth == M) {
        for (int i : arr) {
            stringBuilder.append(i).append(" ");
        }
        stringBuilder.append("\n");
        return;
    }

    for (int i = start; i < N; i++) {
        arr[depth] = i + 1;
        backTracking(depth + 1, M, N, i + 1);
    }
}

오랜만에 뵙습니다. 취준 준비중 생활적 요소가 부족하여
두달가량 일용직 근무를 다녀왔습니다.
다시 천천히 시작해 보려고 합니다. 기다려 주셔서 감사합니다.

 

전체 코드

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


public class Main {

    private static int[] arr;
    private static StringBuilder stringBuilder = new StringBuilder();

    private static void backTracking(int depth, int M, int N, int start) {
        if (depth == M) {
            for (int i : arr) {
                stringBuilder.append(i).append(" ");
            }
            stringBuilder.append("\n");
            return;
        }

        for (int i = start; i < N; i++) {
            arr[depth] = i + 1;
            backTracking(depth + 1, M, N, i + 1);
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        int M = Integer.parseInt(stringTokenizer.nextToken());

        arr = new int[M];


        backTracking(0, M, N, 0);

        System.out.println(stringBuilder);

    }
}