[JAVA]백준 알고리즘 15650번 : N과 M (2)

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

15650번: N과 M (2)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

풀이

백준 알고리즘 15649번 : N과 M (1) 문제와 유사한 문제이다.

다른 점은 위 문제의 두 번째 조건이 추가되었다는 것인데, 이것은 아래의 if문 하나만 추가하면 해결할 수 있다.

 

변경 전 (백준 알고리즘 15649번 : N과 M (1) 문제)

TF[i] = true;
pick[depth] = i + 1;
bt(depth + 1);
TF[i] = false;

변경 후

TF[i] = true;
if(depth == 0 || i + 1 > pick[depth - 1]) {
    pick[depth] = i + 1;
    bt(depth + 1);
}
TF[i] = false;

 

if문은

1. depth가 0일 때(배열에 값을 하나도 넣지 않았을 때)

2. 배열에 넣으려는 값이 이전 항보다 클 때

실행이 되도록 하기 위해 추가하였다.

코드

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

public class Main {
    static int N, M;
    static int[] pick;
    static boolean[] TF;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        pick = new int[M];
        TF = new boolean[N];

        bt(0);
        System.out.println(sb);
    }
    public static void bt(int depth) {
        if(depth == M) {
            for(int i: pick) {
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }

        for(int i = 0; i < N; i++) {
            if(!TF[i]) {
                TF[i] = true;
                if(depth == 0 || i + 1 > pick[depth - 1]) {
                    pick[depth] = i + 1;
                    bt(depth + 1);
                }
                TF[i] = false;
            }
        }
    }
}

틀린 부분이 있다면 정정해주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!