[백준] Silver 3. N과 M(4)

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

15652번: N과 M (4)

 

문제 접근 방법

• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

두가지 조건을 생각하면서 문제를 풀어야 한다.

 

같은 수를 여러 번 골라도 된다 -> 1을 골랐을 때 두번째 값도 동일한 1을 받아야 하므로 재귀 함수를 돌릴 때 i로 돌리면 된다.

 

비내림차순 -> start 파라미터를 통해서 1을 다 순회하고 나면, 그 다음으로 넘어가기 때문에 자동으로 오름차순이 된다.

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

public class Main {

    static int m, n;
    static int [] arr = new int[10];
    static boolean[] visited = new boolean[10];
    static StringBuilder sb = new StringBuilder();
    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());

        recur(1, 0);
        System.out.println(sb.toString());
    }

    private static void recur(int start, int depth) {
        if (depth == m) {
            for(int i = 0; i < m; i++){
                sb.append(arr[i]).append(' ');
            }
            sb.append("\n");
            return;
        }

        for(int i = start; i <= n; i++){
            arr[depth] = i;
            recur(i, depth + 1);
        }
    }
}