[BOJ] 15655 - N과 M (6) JAVA

www.acmicpc.net/problem/15655

15655번: N과 M (6)

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

 

1. 주어진 N개 숫자 중 M개를 고른 수열

2. 오름차순인 수열

 

 

 

codeung.tistory.com/56

[BJ] N과 M (5) JAVA

N과 M (5) 문제에서 오름차순 조건만 추가됨

 

 

 

풀이 .

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 isAsc(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;
        }

        for (int i = 0; i < n; i++) {
            permu[deptNow] = num[i];
            if(check[i] == false && isAsc(deptNow)) {
                check[i] = true;
                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());
        permu = new int[m + 1];
        num = new int[n];
        check = new boolean[n];

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

        for (int i = 0; i < n; i++) {
            if(check[i] == false) {
                permu[0] = num[i];
                check[i] = true;
                dfs(m, 1);
                check[i] = false;
            }
        }

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

 

기존 코드에 isAsc() 하나를 추가하여 해결