[백준 15651] N과 M (3) (자바)

백준 15651번 N과 M (3) (자바)

 

 

출처

www.acmicpc.net/problem/15651

15651번: N과 M (3)

 

 

 

 

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

 

 

 

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

 

 

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

 

입출력 예

입출력 예 1

입출력 예 2

 

 

풀이

1. 중복을 고려할 필요가 없다라는 것을 파악 (!visit[i]) 조건 필요 없음

2. 위 조건을 제외하면 기존 N과 M (1)과 다를 것이 없다.

3. System.out.println()을 사용하면 시간 초과가 나기 때문에 BufferedWriter를 사용해야 한다.

 

- BufferedWriter 사용법 참고

coding-factory.tistory.com/251

 

 

 

내 코드

package brute_force;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class N_15651 {
	
	private static int n, m;
	private static int[] map;
	private static boolean[] visit;
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		//bufferedReader는 런타임 에러뜸. 이유는?
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		
		map = new int[m];
		visit = new boolean[n+1];
		
		cycle(0, 0);
		bw.flush();//남아있는 데이터를 모두 출력시킴
		bw.close();//스트림을 닫음
	}

	private static void cycle(int start, int cnt) throws IOException {
		
		if (cnt == m) {
			
			for (int i=0; i<m; i++) {
				bw.write(Integer.toString(map[i]) + " ");
			}
			bw.newLine();
			
		} else {
			
			for (int i=1; i<=n; i++) {
				visit[i] = true;
				map[start] = i;
				cycle(start + 1, cnt + 1);
				visit[i] = false;
			}
			
		}
	
	}
}

 

 

고려할 점

1. dfs 사용할 것

2. cnt 매개변수를 만들어 m과 동일해지면 출력하도록 한다.