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

1부터 N까지의 자연수 중 M개를 고른 수열을 출력한다. 이때 같은 수를 여러 번 골라도 되고. 고른 수열은 비내림차순이여야한다고 한다.

비내림차순이란

비내림차순이라는 말을 보고 내림차순이 아니니 오름차순인가? 라는 생각을 할 수 도있지만
오름차순과는 약간 다르다.

비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.

그렇기에 N과 M이 주어졌을 때 아래 예제와 같이 출력된다

재귀함수를 만들자

이전의 N과M (3)의 코드에서 수정하여 사용하겠다.

수정 전

    public static void dfs(int num){
        if(num == M){
            for(int i=0;i<M;i++){
                str.append(arr[i]).append(' ');
            }
            str.append('\n');
            return;
        }
        
        for(int i=1;i<=N;i++){
            arr[num] = i;
            dfs(num + 1);
        }
    }  

수정 후

public static void dfs(int from,int num){
        if(num == M){
            for(int i:arr){
                str.append(i).append(' ');
            }
            str.append('\n');
            return;
        }
        
        for(int i=from;i<=N;i++){
            arr[num] = i;
            dfs(i,num + 1);
        }
    }   

이전의 코드에서는 파라미터로 num밖에 없었지만 이번에는 출력을 하면서 앞의 원소보다 크거나 같아야하기 때문에 시작점 변수를 두어 재귀함수를 호출할 수록 1씩 증가하도록 하여 비내림차순 조건에 적합하게 해준다.

전체코드

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

public class Main{
    
    public static int[] arr;
    public static int N,M;
    public static StringBuilder str = new StringBuilder();
    
    
    public static void main(String[] args) throws IOException  {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer strT = new StringTokenizer(br.readLine()," ");
        
        N = Integer.parseInt(strT.nextToken());
        M = Integer.parseInt(strT.nextToken());
        
        arr = new int[M];
        dfs(1,0);
        System.out.println(str);
    }
    public static void dfs(int from,int num){
        if(num == M){
            for(int i:arr){
                str.append(i).append(' ');
            }
            str.append('\n');
            return;
        }
        
        for(int i=from;i<=N;i++){
            arr[num] = i;
            dfs(i,num + 1);
        }
    }   
 }

이 코드를 백준에 제출을 한다면

정답이라는 결과가 나온다.