[완전 탐색] N과 M(1) - 중복허용(오름차순)

1. 문제

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

15652번: N과 M (4)

 

2. 주의사항

• 선택된 이전 값(selected[k-1])을 구할때 인덱스의 시작(0, 1)에 따라서 조회하는 법을 다르게 써야한다.
  • 시작인덱스 1 : 0번째 인덱스의 값은 0이므로 0일때 1로만 치환하면 된다.
  • 시작인덱스 0 : -1번째 인덱스는 존재하지 않으므로(인덱스는 0부터 시작) -1인덱스가 조회되지 않도록 조건을 수정해야한다.

 

 

3.풀이

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

public class Main {
    static StringBuilder sb = new StringBuilder();

    static void input() {
        FastReader scan = new FastReader();
        N = scan.nextInt();
        M = scan.nextInt();
        selected = new int[M];
    }

    static int N, M;
    static int[] selected;
    // Recurrence Function (재귀 함수)
    // 만약 M 개를 전부 고름   => 조건에 맞는 탐색을 한 가지 성공한 것!
    // 아직 M 개를 고르지 않음 => k 번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 시도한다.
    static void rec_func(int k) {
        if(k == M){//모두 골랐다면 출력진행
            for (int i = 0; i < M; i++) {
                sb.append(selected[i]).append(" ");
            }
            sb.append("\n");
        }else {
            int start = k == 0 ? 1: selected[k-1];
            if(start == 0) start = 1;
            for (int j = start; j < N + 1; j++) {//j는 1 ~ N이 선택될 수 있다.
                selected[k] = j;
                rec_func(k + 1);
                selected[k] = 0;
            }
        }
    }

    public static void main(String[] args) {
        input();

        // 0번째 원소부터 M-1 번째 원소를 조건에 맞는 모든 방법을 찾아줘
        rec_func(0);
        System.out.println(sb.toString());

    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}