백준 15649번 N과 M (1)

문제

나의 풀이

import java.util.*;

public class Main {
    static boolean check[] = new boolean[10];
    static int a[] = new int[10];
    static StringBuilder sb = new StringBuilder();
    static void go(int index, int n, int m) {
        if(index == m) {
            for(int i = 0; i < m; i++) {
                sb.append(a[i]);
                if(i != m - 1) {
                    sb.append(" ");
                }
            }
            sb.append("\n");
        }
        
        for(int i = 1; i <= n; i++) {
            if(check[i]) {
                continue;
            }
            check[i] = true;
            a[index] = i;
            go(index + 1, n, m);
            check[i] = false;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        go(0, n, m);
        System.out.println(sb);
    }
}

check 배열과 재귀를 이용해서 풀면 된다.

결과

백준 15650번 N과 M (2)

문제

나의 풀이

import java.util.*;

public class Main {
    static boolean check[] = new boolean[10];
    static int a[] = new int[10];
    static void go(int index, int start, int n, int m) {
        if(index == m) {
            for(int i = 0; i < m; i++) {
                System.out.print(a[i]);
                if(i != m - 1) {
                    System.out.print(" ");
                }
            }
            System.out.println();
            return;
        }

        for(int i = start; i <= n; i++) {
            if(check[i]) {
                continue;
            }
            check[i] = true;
            a[index] = i;
            go(index + 1, i + 1, n, m);
            check[i] = false;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        go(0, 1, n, m);
    }
}

N과 M(1)과는 다르게 1부터 n까지의 수를 모두 for문을 돌리는 것이 아니라 start부터 n까지 for문을 돌려서 앞선 index에 채워진 값 보다는 큰 숫자가 올 수 있도록 구성하게 한다. 다음 수는 현재수보다 큰수 중에 하나이기 때문에 check 배열이 따로 필요 없다.

결과

백준 15651번 N과 M (3)

문제

나의 풀이

import java.util.*;

public class Main {
    static boolean check[] = new boolean[10];
    static int a[] = new int[10];
    static StringBuilder go(int index, int n, int m) {
        if(index == m) {
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < m; i++) {
                sb.append(a[i]);
                if(i != m - 1) {
                    sb.append(" ");
                }
            }
            sb.append("\n");
            return sb;
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= n; i++) {
            check[i] = true;
            a[index] = i;
            sb.append(go(index + 1, n, m));
            check[i] = false;
        }
        return sb;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        System.out.println(go(0, n, m));
    }
}

N과 M (1)에서 중복에 대한 처리를 했던 if(check[i]) continue; 부분을 제거해주면 된다.

결과

백준 15652번 N과 M (4)

문제

나의 풀이

import java.util.*;

public class Main {
    static boolean check[] = new boolean[10];
    static int a[] = new int[10];
    static StringBuilder go(int index, int start, int n, int m) {
        if(index == m) {
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < m; i++) {
                sb.append(a[i]);
                if(i != m - 1) {
                    sb.append(" ");
                }
            }
            sb.append("\n");
            return sb;
        }

        StringBuilder sb = new StringBuilder();
        for(int i = start; i <= n; i++) {
            check[i] = true;
            a[index] = i;
            sb.append(go(index + 1, i, n, m));
            check[i] = false;
        }
        return sb;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        System.out.println(go(0, 1, n, m));
    }
}

N과 M(2)에서 중복만 허용하는 조건이 추가된 것이므로 if(check[i]) continue; 구문만 삭제하면 된다.

결과

백준 15654번 N과 M (5)

문제

나의 풀이

import java.util.*;

public class Main {
    static boolean check[] = new boolean[10];
    static int a[] = new int[10];
    static int num[] = new int[10];
    static StringBuilder go(int index, int n, int m) {
        if(index == m) {
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < m; i++) {
                sb.append(num[a[i]]);
                if(i != m - 1) {
                    sb.append(" ");
                }
            }
            sb.append("\n");
            return sb;
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            if(check[i]) {
                continue;
            }
            check[i] = true;
            a[index] = i;
            sb.append(go(index + 1, n, m));
            check[i] = false;
        }
        return sb;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        for(int i = 0; i < n; i++) {
            num[i] = sc.nextInt();
        }
        Arrays.sort(num, 0, n);
        System.out.println(go(0, n, m));
    }
}

N과 M(1)에서 num배열을 추가하여 숫자를 입력 받고, 정렬을 시키는 부분만 추가하면 된다.

결과

백준 15655번 N과 M (6)

문제

나의 풀이

import java.util.*;

public class Main {
    static boolean check[] = new boolean[10];
    static int a[] = new int[10];
    static int num[] = new int[10];
    static StringBuilder go(int index, int start, int n, int m) {
        if(index == m) {
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < m; i++) {
                sb.append(num[a[i]]);
                if(i != m - 1) {
                    sb.append(" ");
                }
            }
            sb.append("\n");
            return sb;
        }

        StringBuilder sb = new StringBuilder();
        for(int i = start; i < n; i++) {
            if(check[i]) {
                continue;
            }
            check[i] = true;
            a[index] = i;
            sb.append(go(index + 1, i + 1, n, m));
            check[i] = false;
        }
        return sb;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        for(int i = 0; i < n; i++) {
            num[i] = sc.nextInt();
        }
        Arrays.sort(num, 0, n);
        System.out.println(go(0, 0, n, m));
    }
}

N과 M(2)에서 num배열을 추가하여 숫자를 입력 받고, 정렬 시키는 부분만 추가하면 된다.

결과