[백준] 15652번 N과 M (4)

알고리즘 문제

[백준] 15652번 N과 M (4)

feelcoding 2020. 1. 6. 19:26

728x90

N과 M (4)는 중복조합 문제이다.

15652번: N과 M (4)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

www.acmicpc.net

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

public class Main{
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = "";
        StringBuilder sb = new StringBuilder();
        try {
            s = br.readLine();
        } catch (IOException e) {}
        StringTokenizer st = new StringTokenizer(s);
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] result = new int[m];
        permutationWithRepetition(n, m, 0, result, sb);
        System.out.println(sb);
    }
    static void permutationWithRepetition(int n, int m, int num, int[] result, StringBuilder sb) {
        if (num == m) {
            for (int i = 0; i < m; i++) {
                sb.append(result[i] + " ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 0; i < n; i++) {
            if(num != 0 && result[num - 1] > i + 1)
                continue;
            else {
                result[num] = i + 1;
                permutationWithRepetition(n, m, num + 1, result, sb);
            }
        }
    }
}

N과 M (3)과 똑같은 코드에

if(num != 0 && result[num - 1] > i + 1)
    continue;

이 조건만 추가해줬다.

728x90