[BOJ] 15652 - N과 M (4) JAVA

www.acmicpc.net/problem/15652

15652번: N과 M (4)

1~N 의 자연수를 사용 하여 나타낼 수 있는 M자리 수열을 모두 출력해야한다. (숫자들의 중복 사용 허용)

단, 내림차순이 아닌 수열들만 출력한다.

출력하는 수열들의 순서는 사전 순 오름차순으로 한다.

 

 

codeung.tistory.com/54

[BJ] N과 M (3) JAVA

N과 M (3) 에서 '비 내림차순' 조건만 추가되었다.

 

 

 

풀이 .

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 int[] permu = null;
    static int n, m;

    public static boolean isNotDesc(int len) {
        for (int i = 0; i < len; 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 = 1; i <= n; i++) {
            permu[deptNow] = i;
            if (isNotDesc(deptNow)) {
                dfs(dept, deptNow + 1);
            }
        }
    }

    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];

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

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

 

N과 M (3) 코드에서 isNotDesc() 하나만 추가되었다.

 

dfs를 재귀하기 전 검사를 통해 조건에 맞지 않는 수열로의 재귀를 막았다.