백준 N과 M(4)_(15652)

⭐문제링크

이번엔 N과 M 4이다.
이번 문제는 같은 수는 여러번 고를 수 있지만 비내림차순이어야 한다.

바뀐 코드는 다음과 같다.

for(int i=start; i<N; i++) {
            array[depth] = i+1;
            dfs(i, depth+1);
        }

N과 M(2) 에서는 중복을 없애기 위하여 dfs 재귀호출을 하는 부분의 start에 i+1을 해주었었다.

위와 같이 코드를 진행하면 array의 다음 원소는 무조건 전 인덱스로의 원소보다 큰 값에서 시작하기에 해당 조건을 만족할 수 있었다.

그렇다면 만약 전 인덱스의 원소와 같거나 큰 값이어야 한다면?

간단하다. i+1이 아닌 그냥 i를 넘겨주면 된다.

즉 최종 코드는 아래와 같다.

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

public class Main {
    static int N;
    static int M;
    static int array[];

    static StringBuilder answer = 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());

        array = new int[M];

        dfs(0, 0);
        System.out.println(answer);
    }

    public static void dfs(int start, int depth) {
        if(depth==M) {
            for(int val : array){
                answer.append(val+" ");
            }
            answer.append("\n");
            return;
        }

        for(int i=start; i<N; i++) {
            array[depth] = i+1;
            dfs(i, depth+1);
        }
    }

}