[15650] N과 M(2) - Java

백준 N과 M(2) (실버 Ⅲ)

 

1. 가지치기

import java.util.Scanner;

public class Main {
    static int n;
    static int m;
    static int[] path = new int[9];
    static boolean[] used = new boolean[9];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        run(0, 0);
        System.out.println(sb);
    }

    private static void run(int level) {
        if(level > 1 && path[level - 1] < path[level - 2]) return;
        if(level == m) {
            for(int i = 0; i < m; i++) {
                sb.append(path[i] + " ");
            }
            sb.append("\n");
            return;
        }

        for(int i = 1; i <= n; i++) {
            if(!used[i]) {
                path[level] = i;
                used[i] = true;
                run(level + 1);
                path[level] = 0;
                used[i] = false;
            }
        }
    }
}

if(level > 1 && path[level - 1] < path[level - 2]) return;

path 배열이 오름차순이 아니면 가지치기를 한다.

 

2.  start 변수를 추가해서 반복문 시작(i값)이 다음에 실행될 때 1씩 늘어나게 해주기

import java.util.Scanner;

public class N과M_2 {
    static int n;
    static int m;
    static int[] path = new int[9];
    static boolean[] used = new boolean[9];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        run(1, 0);
        System.out.println(sb);
    }

    private static void run(int start, int level) {
        if(level == m) {
            for(int i = 0; i < m; i++) {
                sb.append(path[i] + " ");
            }
            sb.append("\n");
            return;
        }

        for (int i = start; i <= n; i++) {
            path[level] = i;
            run(i + 1, level + 1);
            path[level] = 0;
        }
    }
}

for (int i = start; i <= n; i++) {
    path[level] = i;
    run(i + 1, level + 1);
    path[level] = 0;
}

start 변수를 재귀 함수에 추가해서 +1씩 되게 해준다.