개요

간단한 백트래킹 문제
하라는데로 하면 된다.

N과M(8)

문제분석

문제를 보면, 조건이 좀 달려있다.
하나씩 뜯어보자

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

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

1. 주어진 N개의 자연수들 중,길이가 M인 수열을 모두 구해야한다
   즉, N개의 수중 M개를 선택해야한다. 여기에서 더 보아야 할 조건은 같은 수를 여러번 골라도 된다는 것이다.
   중복이 가능하다는 말이다.

2. 비내림차순이어야한다. 이 말이 좀 이상한것같은데 그냥 오름차순으로 정렬되면 된다는 말로 이해했다.
   A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK 의 형태로, 오른쪽으로 갈 수록 숫자가 더 커지거나 혹은 같은 형태의 수열을 가지면 된다는 말과 동일하다.
   나는 이 처리를 위해서 input으로 들어오는 배열을 먼저 정렬해주었다.
   정렬을 미리 해주면, 중복 순열을 구하는 과정에서 이미,오름차순으로 재귀를 하기 때문에 오름차순에 대한 문제가 없다.
   마지막으로 다음 원소가 크거나 같아야 하기 때문에, 이 조건을 만족하기 위해 중간에 조건을 따로 추가해주었다. depth가 0일 경우에는 시작점이기 때문에 비교할 원소가 없기 때문에 그냥 재귀문을 돌렸다.

문제풀이

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

/**
 * @author onyoo
 * @performance
 * @category
 * @note
 * n개의 자연수 중에서 m개를 고른 수열
 * 같은 수를 여러번 골라도 된다 -> 중복 가능
 * 비내림차순 (=오름차순) -> A1 <= A2 <= Ak-1 <= Ak
 * @see
 * https://www.acmicpc.net/problem/15657
 * @since 2023-10-26
 **/
public class N과M {
    static int n,m;
    static int[] arr;

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

        st = new StringTokenizer(br.readLine()," ");

        for(int i=0;i<n;i++) arr[i] = Integer.parseInt(st.nextToken());
        
        Arrays.sort(arr);
        
        dfs(0,new int[m]);

    }
    static void dfs(int depth,int[] a){
        if(depth == m){
            StringBuilder sb = new StringBuilder();
            for(int value : a){
                sb.append(value + " ");
            }
            System.out.println(sb);
            return;
        }
        for(int i=0;i<arr.length;i++){
            a[depth] = arr[i];
            if(depth != 0){
                if(a[depth-1] <= a[depth]) dfs(depth+1,a);
            }
            else{
                dfs(depth+1,a);
            }
            a[depth] = 0;
        }
    }
}