[백준,BOJ 15652] N과 M(4) (JAVA 구현,추가풀이)

-내 생각

  백준 온라인 저지에서 단계별 풀어보기 탭의 백트래킹 카테고리에 있는 마지막 N과 M문제이다. 이번 문제가 가지는 앞선 문제들과의 차이점은 우선 중복을 허용하며, 각 자리의 숫자들은 자신보다 앞에 있는(먼저 오는) 숫자보다 크거나 같아야 한다는 조건이 있다. 그렇기 때문에 처음 봤을 때 N과 M(3) 문제에서 조건만 추가해주면 될 것 같다고 생각했으며, 시간제한이 1초이기 때문에 마찬가지로 BufferedWriter클래스와 BufferedReader클래스를 사용해주었다.

 

-해법

  추가된 한 줄의 조건문은 코드를 보면서 이해해 보자.

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

public class Main {
	static int m,n;
	static int list[];
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static void dfs(int cnt) throws IOException {
		
		
		if(cnt == m) {
			for(int i=0;i<m;i++) {
				bw.write(String.valueOf(list[i])+" ");			
				}
			bw.newLine();
			return;
		}
		
		for(int i =1;i<=n;i++) {
			if(cnt!=0 && list[cnt-1]>i) continue; //추가 된 조건부
            //이 부분을 제외하고는 N과 M(3)문제와 동일하다.
            // cnt!=0인 이유는 자신보다 앞의 숫자가 있는 경우는 2번째 자리 숫자부터이기 때문이다.
			list[cnt]=i;		
			dfs(cnt+1);			
		}	
	}
	
	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());
		
		
		list = new int [m];
		dfs(0);
		br.close();
		bw.flush();
		bw.close();
	}
	
}

 

---

  앞선 N과 M (2), N과 M (3)을 합친 듯한 문제이다. 그렇기에 풀이 역시 두 가지 문제를 고려해 추가했던 부분을 작성해주면 된다.

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

class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static int n,m;	
    
	static void dfs(int[] a,int v,int cnt) throws IOException {
		if(cnt == m) {
			for(int i=0;i<m;i++) {
				bw.write(String.valueOf(a[i]+" "));
			}
			bw.newLine();
			
			return;
		}
		
		// 중복을 고려하지 않기 위해 check배열을 사용하지 않고,
        // 앞선 숫자 뒤에 오는 숫자는 자신보다 크거나 같은 숫자들이 위치해야 하므로 인자를 하나 더 넘겨준다.
        // 넘겨받은 인자부터 반복문을 수행하면 해결.
		for(int i=v;i<=n;i++) {		
				a[cnt] = i;
				dfs(a,i,cnt+1);			
		}
	}
	
	public static void main(String[] args) throws IOException  {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		int a[] = new int[m];
		
		
		dfs(a,1,0);
		
		bw.flush();
		bw.close();
		br.close();
		
	}
}