[백준][15652번] N과 M(4)

문제 URL

https://www.acmicpc.net/problem/15652

내풀이

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] ans;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        ans = new int[m];
        cal(1, 0, n, m);
        bw.flush();
        bw.close();
    }
    //idx: 숫자
    //selectd:: 지금까지 선택된 수의 개수
    public static void cal(int idx, int selected, int n, int m) throws IOException {
        if (selected == m) {
            StringBuilder sb = new StringBuilder();
            for (int a : ans)
                sb.append(a + " ");
            bw.write(sb.toString());
            bw.newLine();
            return;
        }
        if (idx > n) return;
        //수를 선택
        ans[selected] = idx;
        cal(idx, selected + 1, n, m);
        //수를 선택하지 않을경우
        ans[selected] = 0;
        cal(idx + 1, selected, n, m);
    }
}

다른 풀이법(순서관점) **

import java.util.*;
public class Main {
    static boolean[] c = 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 ans = new StringBuilder();
        for (int i=start; i<=n; i++) {
            //if (c[i]) continue;
            c[i] = true;
            a[index] = i;
            ans.append(go(index+1, i, n, m));
            c[i] = false;
        }
        return ans;
    }   
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        System.out.print(go(0,1,n,m));
    }
}

다른 풀이법(선택관점) **

import java.util.*;
public class Main {
    static int[] cnt = new int[10];
    //idx: 숫자
    //selectd:: 지금까지 선택된 수의 개수
    static StringBuilder go(int index, int selected, int n, int m) {
        if (selected == m) {
            StringBuilder sb = new StringBuilder();
            for (int i=1; i<=n; i++) {
                for (int j=1; j<=cnt[i]; j++) {
                    sb.append(i);
                    sb.append(" ");
                }
            }
            sb.append("\n");
            return sb;
        }
        StringBuilder ans = new StringBuilder();
        if (index > n) return ans;
        // m-selected 에서 1까지 감소하는 순으로 한 이유는
        // 문제에서 전체수열 정렬해서 출력하라고해서
        for (int i=m-selected; i>=1; i--) {
          //cnt[i] = 수 i를 몇개포함
            cnt[index] = i;
            ans.append(go(index+1, selected+i, n, m));
        }
        cnt[index] = 0;
        ans.append(go(index+1, selected, n, m));
        return ans;
    }   
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        System.out.print(go(1, 0, n, m));
    }
}

느낀점

전형적인 브루트포스다. 앞에푼 N과M문제의 변형이 계속 나온다.

• 풀이법(선택관점) 각각의 자연수를 선택하는 경우와 선택하지 않는경우가 있다. 하지만, 중복선택가능하기 떄문에, 선택하는 경우를 i개 선택하는 경우로 세분화해야한다.
• 시간복잡도 : O(2n)