21.04.18 - [BOJ] 15650. N과 M(2)

[suhyunsim]

문제

• 15650

핵심 아이디어

순서

• start: index 번째에 올 수 있는 수는 start - n
• start가 생겨서 절대로 중복 값을 사용할 일이 없으니 c배열은 필요 없어짐

선택

• 오름차순 -> 선택과 관련한 문제로 풀이할 수 있음
• 선택의 관점에서는 위치가 중요하지 않음, 그 수가 중요함
• index: 수 index
• selected: 선택한 수의 개수
• 수 index를 선택
  • index -> index + 1
  • selected -> selected + 1
• 수 index를 선택 X
  • index -> index + 1
  • selected -> 변함 없음
• O(2^N)

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q15650;

import java.util.Scanner;

public class Main {
    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++) {
            a[index] = i;
            go(index + 1, i + 1, n, m);
        }
    }

    //선택으로 풀이
    static void go(int index, int selected, int n, int m) {
        if (selected == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(a[i]);
                if (i != m - 1) System.out.print(' ');
            }
            System.out.println();
            return;
        }
        if (index > n) return;
        //선택했을 때
        a[selected] = index;
        go(index + 1, selected + 1, n, m);
        //선택하지 않았을 때
        a[selected] = 0;
        go(index + 1, selected, n, m);
    }

    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);
        //선택
        go(1, 0, n, m);
    }
}