[완전 탐색] N과 M(3) - 중복허용

1. 문제

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

15651번: N과 M (3)

 

2. 주의사항

• selected배열에 선택한 값 N을 넣을 때 배열의 시작이 0인지, 1인지에 따라서 자연수 N선택하는 for문, 최종적으로 출력하기 위한 비교연산(k ==m)이 달라지므로 을 헷갈리면 안된다.
• N(자연수)을 선택하는 for문의 시작값은 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 {
            for (int j = 1; 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;
        }
    }
}