[BAEKJOON] 15650 N과 M (2)

문제 요약

• 알고리즘 분류: 백트래킹
• 난이도: Silver3
• 문제내용:
  • N, M 가 주어 졌을때 1 ~ N수 에서 중복없이  M개를 뽑을때
  • 나올수 있는 수를 모두 출력해라.
• 사이트 주소: https://www.acmicpc.net/problem/15650

15649번: N과 M (1)

문제풀이

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

https://jih3508.tistory.com/84

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

https://jih3508.tistory.com/28

[BAEJOON] 15649 N과 M (1)

 위에 있는 문제랑 비슷한데 이번에는 순열이 아니라 조합이다. 파이썬에는 조합을 구현을 도와주는 combination 함수가 있지만 다른언어는 없어서 백트래킹으로 풀어야 한다,

 N과 M(1) 문제는 숫자가 있는지 없는 지판단해서 추가 했지만 이번문제는 순서대로 나올수있는 수를 구해야 하기 때문에 반복문에 이전에 저장했던 수보다 큰것을 넣으면 되서 중간 조건문이 필요없다. 

1. N, M을 설정한다.
2. 파이썬은 값을 담을 리스트만 선언하고 그  외의 언어는 값을 담을 배열로 선언한다.
3. 0부터 시작해서 M까지 재귀 호출할 함수를 만든다.
4. M까지 갔을 경우 값을 담은 배열/리스트를 출력한다.
5. 그 외 경우 이전에 저장했던 숫자보다 큰 수자를 N까지 루프를 돌려서 배열 또는 리스트에 저장한다음 함수 재호출 한다.

CODE

Java

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static int[] array;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		array = new int[M];
		NM(1, 0);
		System.out.println(sb);
		
	}
	
	public static void NM(int k, int depth) {
		if(depth == M) {
			for(int i = 0; i < M; i++) {
				sb.append(array[i] + " ");
			}
			sb.append("\n");
		}else {
			for(int i = k; i <= N; i++) {
				array[depth] = i;
				NM(i + 1, depth + 1);
			}
		}
		
	}
		
}

Python

Backtraking

def NM(k, array):
    if len(array) == M:
        print(' '.join(map(str, array)))
    else:
        for i in range(k, N + 1):
            NM(i + 1, array + [i])

N, M = map(int, input().split())
NM(1, [])

Combinations

from itertools import combinations

N, M = map(int, input().split())
array = list(range(1, N+1))
for item in combinations(array, M):
    print(' '.join(map(str, item)))