[Java] BOJ15650, 백준 - N과 M(2)

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

15650번: N과 M (2)

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

 

출력

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

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

 

<풀이>

앞에서 푼 N과 M(1)과 다 똑같은데, 수열이 오름차순의 조건을 만족해야한다는 조건이 추가되었다.

그래서 이전의 소스코드에 오름차순으로만 진행될 수 있도록 start라는 매개변수를 추가하여 go함수가 어떤 수부터 시작할지 정해주었다.

 

1차 코드

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

public class Main {
	private static int n;
	private static int m;
	private static boolean[] check;
	private static int[] arr;
	private static StringBuilder sb = new StringBuilder();

	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());
		check = new boolean[n + 1];
		arr = new int[n + 1];
		go(1, 1);
		System.out.println(sb);
	}

	private static void go(int cnt, int start) {
		if (cnt > m) { // 종료조건, M만큼 출력했을 때
			append();
			return;
		}

		for (int j = start; j <= n; j++) {
			if (check[j])
				continue;
			check[j] = true;
			arr[cnt] = j;
			go(cnt + 1, j + 1);
			check[j] = false;
		}
	}

	private static void append() {
		for (int i = 1; i <= n; i++) {
			if (arr[i] != 0)
				sb.append(arr[i] + " ");
		}
		sb.append("\n");
	}
}

 

2차 코드

1. check 배열은 이전에 이 수를 사용했는지 아닌지를 검사하기 위한 배열이다. 그래서 N과 M(1) 문제에서는 필요했지만 이번 문제에서는 오름차순으로만 진행해야하기 때문에 이전의 숫자(더 작은 숫자)로 돌아갈 필요가 없고, 즉 검사할 필요도 없다. 그래서 check배열을 선언하는 부분과 사용하는 부분 모두 없애줄 수 있다.

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

public class Main {
	private static int n;
	private static int m;
	private static int[] arr;
	private static StringBuilder sb = new StringBuilder();

	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];
		go(1, 1);
		System.out.println(sb);
	}

	private static void go(int cnt, int start) {
		if (cnt > m) { // 종료조건, M만큼 출력했을 때
			append();
			return;
		}

		for (int j = start; j <= n; j++) {
			arr[cnt] = j;
			go(cnt + 1, j + 1);
		}
	}

	private static void append() {
		for (int i = 1; i <= n; i++) {
			if (arr[i] != 0)
				sb.append(arr[i] + " ");
		}
		sb.append("\n");
	}
}

 

N과 M 3과 4도 여기서 조금만 응용하면 금방 풀 수 있다

 

 

+3차 코드

또다른 풀이

중복X, 수를 M개 선택해서 오름차순인 수열을 만들어야 한다

즉, N개의 수 중 M개의 조합을 고르기만 하면 그 수에서 만들 수 있는 오름차순 순열은 하나 뿐이다.

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

public class Main {
	private static int n;
	private static int m;
	private static int[] arr;
	private static StringBuilder sb = new StringBuilder();

	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];
		go(1, 1);
		System.out.println(sb);
	}

	private static void go(int cnt, int idx) {
		if (cnt > m) { // 종료조건, M만큼 출력했을 때
			append();
			return;
		}

		if (idx > n)
			return;

		arr[cnt] = idx;
		go(cnt + 1, idx + 1);
		arr[cnt] = 0;
		go(cnt, idx + 1);
	}

	private static void append() {
		for (int i = 1; i <= n; i++) {
			if (arr[i] != 0)
				sb.append(arr[i] + " ");
		}
		sb.append("\n");
	}
}