[백준 15651] N과 M (3)

N과 M(1) 풀이 링크
N과 M(2) 풀이 링크

문제 설명

이번 문제와 앞선 N과 M문제들의 다른 점은 중복선택이 가능하다는 것이다.

생각 정리

그럼 방문체크를 안하면 되는거 아닌가 ??

앞선 N과 M 문제들에서 방문체크를 했던 이유는 중복없이 고르기 위해서 이 숫자를 내가 선택했는지 체크하기 위함이었다.

그런데 중복이 허용된다면 ? 방문체크를 할 필요가 없어 보인다!

정리된 생각에 대한 논리

시간초과가 나왔다.
System.out.print가 아니라, BufferedWriter로 한번에 출력하니 문제가 해결되었다.

완성

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

public class BOJ15651 {
    static int arr[];
    static boolean visited[];
    static int N, M;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N+1];
        visited = new boolean[N+1];

        func(0);
        
        bw.flush();
        bw.close();
    }
    
    static void func(int current) throws IOException {
        if(current == M){
            for(int i=0; i<M; i++)
                bw.write((arr[i]+1) + " ");
            bw.write("\n");
            return ;
        }

        for(int i=0; i<N; i++) {
            arr[current] = i;
            func(current+1);
        }
    }
}