[BAEKJOON]15657 N과 M (8)

문제 요약

• 알고리즘 분류: 백트래킹
• 난이도: Silver3
• 문제내용:
  • 같은 수를 여러 번 골라도 된다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하고 M개의 수열을 사전순으로 출력해라.
• 사이트 주소: https://www.acmicpc.net/problem/15657

15657번: N과 M (8)

문제풀이

 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다.

https://jih3508.tistory.com/84

[알고리즘 이론] 백트래킹(Backtracking)

접근 방법 

  이번에 출력순서가 a1 <= a2 <= a3 순으로 수열을 나올수 있는 경우의 수가 내림 차순으로 출력하도록 해야한다. 그러기 위해서 배열을 선언하고 정렬을 한 다음과 같이 재귀호출을 작성하면된다.

1. 방문 체크할 visited 선언한다.
2. 재귀 호출할 함수를 만든다.
   • 재귀 호출 파라미터를 M개까지 수열을 카운터할 변수K와  인덱스 위치 지정할 변수인 함수 x를 만든다.
   • 0부터 시작해서 K가 M이랑 같으면 수열을 출력한다,.
   • K가 M 미만이면 인덱스 x부터 for문을 돌린다.(초기에 x 0부터 시작)
   • for문안에서 재귀호출을 할때 (K + 1, 반복문 지점)넘기면서 호출한다.

Code

Python

def NM(x, p =[]):
    if(len(p) == M):
        print(' '.join(map(str, p)))
        return
    for i in range(x, N):
        NM(i, p + [array[i]])
        
N, M = map(int, input().split())
array = sorted(list(map(int, input().split())))
NM(0)

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
		
	static int[] array, result;
	static int N, M;
	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());
		st = new StringTokenizer(br.readLine());
		array = new int[N];
		result = new int[M];
		for(int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		// 내림차순으로 출력하기 위해서 배열 정렬
		Arrays.sort(array);
		
		NM(0, 0);
		System.out.println(sb);
	}
	
	public static void NM(int k, int x) {
		if (k == M) {
			for(int i = 0; i < M; i++) {
				sb.append(result[i]).append(" ");
			}
			sb.append("\n");
			return ;
		} 
		
		// 출력 a1 <= a2 <= a3 처리 하기 위해서 인덱스 a1 부터 시작하도록 한다. 
		for(int i = x; i < N; i++) {
			result[k] = array[i];
			NM(k + 1, i);
		}
	}

}