[BAEKJOON] 15651 N과 M (3)

문제 요약

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

15651번: N과 M (3)

문제풀이

https://jih3508.tistory.com/28

[BAEJOON] 15649 N과 M (1)

https://jih3508.tistory.com/30

[BAEJOON] 15650 N과 M (2)

 이번 문제도 백트래킹인데 그냥 재귀호출만 작성할줄 아면 금방 풀수 있는 문제이다. 그래서 위에 문제보다 더 쉽게 풀수가 있다. 그 이유는 이번에는 각 수열에 수가 중복이 허용되서 for문으로 1 ~ N 까지 각 index에 넣으면 되기 때문이다.  이번 문제는 재귀호출 개념만 알면 되기 때문에 이 블로그에서는 따로 풀이를 설명을 안할것이다. 

 

Code

Python

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

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

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( 0);
		System.out.println(sb);
		
	}
	
	public static void NM(int depth) {
		if(depth == M) {
			for(int i = 0; i < M; i++) {
				sb.append(array[i] + " ");
			}
			sb.append("\n");
		}else {
			for(int i = 1; i <= N; i++) {
				array[depth] = i;
				NM(depth + 1);
			}
		}
		
	}
		
}