(Java) 백준 15657번 - N과 M (8)

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

문제

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

> N개의 자연수 중에서 M개를 고른 수열
> 같은 수를 여러 번 골라도 된다.
> 고른 수열은 비내림차순이어야 한다.
> 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

접근

백트래킹을 사용해 모든 조합을 만들어나간다.
문제에서 주어진 비내림차순은 다시 말해 같은 수거나, 오름차순이 되는 수열을 말한다.
따라서 입력받은 자연수를 정렬한 뒤, 재귀로 들어가서 돌아가는 반복문의 초기값으로 비 내림차순이 되도록 현재와 같은 인덱스를 전달해준다.

문제해결

> N과 M을 입력받고 크기 N인 배열에 자연수를 입력받고 결과 수열을 저장할 배열도 크기 M으로 선언한다.
> 수를 입력받았으면 비내림차순을 위해 오름차순으로 정렬해준다.
> 백트래킹으로 가능한 수열을 뽑는 NtoM메소드에 수열의 첫수부터, 결과배열의 원소수로 각각 0,0을 전달해준다.
> NtoM메소드에서 입력받은 idx값 부터 반복문을 돌며 수를 뽑고 저장하며 재귀로 들어간다.
> 계속 재귀로 들어가다 if문에서 걸리면, 즉 원하는 길이가 만들어지면 저장된 수열을 출력한다.
> 재귀전으로 돌아가 반복문의 다음 i를 실행해 다른 경우를 탐색한다.

코드

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main {
    //15657번 N과 M (8)
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int N, M;
    static int[] num;
    static int[] result;
    static void NtoM(int idx, int rst) {
        if(rst == M) {
            for(int i : result) {
                sb.append(i).append(' ');
            }
            sb.append('\n');
            return;
        }
        for(int i = idx; i < N; i++) {
            result[rst] = num[i];
            NtoM(i, rst + 1);
        }
    }
    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        num = new int[N];
        result = new int[M];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) num[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(num);

        NtoM(0,0);
        System.out.print(sb);
    }
}

후기

계속 결과가 0만 나와서 분명 제대로 했는데 뭐가 문제인지 했더니 main에서 전역으로 선언했던 N과 M을 다시 int N과 int M으로 선언해줘서 그랬다.