21.04.24 - [BOJ] 15652. N과 M(4)

[suhyunsim]

문제

• 15652

핵심 아이디어

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 중복선택 가능
• 비내림차순
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
• 비내림차순만 고르는 것이기 때문에, 다른 방식도 가능하다.
• 각각의 자연수를 선택하는 경우와 선택하지 않는 경우가 있다.
• 하지만, 중복 선택이 가능하기 때문에, 선택하는 경우를 i개 선택하는 경우로 세분화해야 한다

어려운 점, 실수

• 순서로 푸는 방법은 무리없이 풀었는데 선택해서 풀려고 하니까 어려웠다.

풀이

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

import java.util.Scanner;

public class Main {
    static int[] a = new int[10];
    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));
*/
//        선택으로 풀이
        System.out.println(go(1, 0, n, m));
    }

/*    순서로 풀이
    private 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++) {
            a[index] = i;
            //순서로 풀이
            ans.append(go(index + 1, i, n, m));
        }
        return ans;
    }
 */
    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 <= a[i]; j++) {
                    sb.append(i);
                    sb.append(" ");
                }
            }
            sb.append("\n");
            return sb;
        }
        StringBuilder ans = new StringBuilder();
        if (index > n) return ans;
        for (int i = m - selected; i>= 1; i--) {
            a[index] = i;
            ans.append(go(index + 1, selected + i, n, m));
        }
        a[index] = 0;
        ans.append(go(index + 1, selected, n, m));
        return ans;
    }
}