[BOJ] 15664 - N과 M (10) JAVA

www.acmicpc.net/problem/15664

15664번: N과 M (10)

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

 

1. 입력받은 N개 중 M개의 숫자를 고른 수열

2. 숫자는 여러번 사용될 수 없음. 단, 똑같은 숫자를 여러번 입력받은 경우는 각각을 다른 숫자로 취급

3. 여러번 입력받은 똑같은 숫자를 다른 숫자로 취급하긴 하지만 수열의 같은 자리에 대해서는 같은 숫자로 취급

즉, 중복 수열은 허용하지 않는다.

4. 비내림차순인 수열만 혀용한다.

 

 

 

codeung.tistory.com/60?category=449370

[BJ] N과 M (9) JAVA

N과 M (9) 에서 비내림차순 조건만 추가된 문제

 

 

 

 

풀이 .

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;
    static boolean[] check = null;
    static int[] permu = null;
    static int[] num = null;
    static int n, m;

    public static boolean isNotDesc(int deptNow) {
        for (int i = 0; i < deptNow; i++) {
            if (permu[i] > permu[i + 1]) {
                return false;
            }
        }
        return true;
    }

    public static void dfs(int dept, int deptNow) {
        if (dept == deptNow) {
            for (int i = 0; i < dept; i++) {
                sb.append(permu[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        Set<Integer> used = new HashSet<>();
        for (int i = 0; i < n; i++) {
            permu[deptNow] = num[i];
            if (!check[i] && !used.contains(num[i]) && isNotDesc(deptNow)) {
                check[i] = true;
                used.add(num[i]);

                dfs(dept, deptNow + 1);
                check[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        check = new boolean[n];
        permu = new int[m + 1];
        num = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(num);

        Set<Integer> used = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (!check[i] && !used.contains(num[i])) {
                check[i] = true;
                used.add(num[i]);
                permu[0] = num[i];

                dfs(m, 1);

                check[i] = false;
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

 

기존 코드에서 isNotDesc() 를 추가하여 해결