백준 15651번 N과 M (3)

백준 15651번 N과 M (3) 문제이다.

문제는 다음과 같다. 이전 N과 M 문제들과 비슷하다.

이번에는 중복이 허용되어 있다.

역시 같은 백트래킹 문제이다. 

이번에는 중복이 허용되기 때문에 check 배열이 필요가 없다.(만들어놓고 쓰질 않았다...)

그대로 모든 경우를 돌려 수열이 완성되면 출력하도록 만들어주었다. 

언어는 java를 이용하였다.

입출력을 System을 이용하여 했더니 시간초과가 나와서 Buffer를 사용해주었다.

백준에서 풀때는 항상 이 방법을 사용하도록 해야겠다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;


public class Main {

    static int n, m;
    static int[] arr1 = new int[8];
    static int[] arr2 = new int[8];
    static int[] check = new int[8];
    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 ) );
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
    
        for(int i = 0; i < n; i++){
            arr1[i] = i + 1;
        }
        func(0);
        bw.flush();
        bw.close();
        
    }
    public static void func(int cnt)throws IOException{
        
        if(cnt == m){
            for(int i = 0; i < m; i++){
                String t = String.valueOf(arr1[arr2[i]]);
                bw.write(t + ' ');
            }
            bw.write('\n');
        }          
        else{  
            for(int i = 0; i < n; i++){
                arr2[cnt] = i;
                func(cnt+1);
            }
        }
    }
    
}

중복이 허용되기때문에 조건을 뺀 것이라 이전 N과 M을 풀었다면 쉽게 풀 수 있었을 것이다.

성공!