[백준BOJ] 15657번 N과 M(8).java

 

백준 저지에서 N과 M(8)을 자바를 통해 풀어 보았다. 

 

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

15657번: N과 M (8)

 

15657번 N과 M(8).java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

15657번 N과 M(8)

문제

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

- N개의 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
- 고른 수열은 비내림차순이어야 한다.
   - 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

설명

N과 M 시리즈는 대부분 백트래킹을 사용하면서 조건만 조금씩 바뀌는 문제라 다른 N과 M을 풀었다면 어렵지 않았을 것이다.

 

백트래킹을 통해 푸는 문제이며 중복을 허용하는 비내림차순 순열을 만들면 된다.

 

중복을 허용하므로 visit 배열은 사용하지 않았으며 배열간의 크기만 비교했다.

코드

//15657번 N과 M(8).java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class N과_M8_15657 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[] num = new int[N];
		st = new StringTokenizer(br.readLine()," ");
		for(int i=0;i<N;i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(num);
		backtracking(num, N, M, 0, new int[N]);
		System.out.println(sb.toString());
	}
    static void backtracking(int[] num, int N, int M,int count, int[] arr) {
    	if(count==M) {
    		for(int i=0;i<M;i++)sb.append(arr[i]+" ");
    		sb.append("\n");
    		return;
    	}
    	for(int i=0;i<N;i++) {
    		if(count==0 || num[i]>=arr[count-1]) {
    			arr[count] = num[i];
    			backtracking(num, N, M, count+1, arr);
    		}
    	}
    }
}