[BAEKJOON] 15652 N과 M (4)

문제 요약

• 알고리즘 분류: 백트래킹
• 난이도: Silver3
• 문제내용:
  • N, M 가 주어 졌을때 1 ~ N수 에서 똑같은 숫자 여러번 출력해도 된다.
  • 중복되는 수열은 여러번 출력하면 안된다.
• 사이트 주소: https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

문제풀이

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

https://jih3508.tistory.com/84

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

 이번 문제도 아래 문제랑 비슷한 유형이다.

https://jih3508.tistory.com/32

[BAEJOON] 15651 N과 M (3)

 다만 앞에 숫자보다 작게 출력은 하면 안되서 이전 코드에서 조금만 수정 하면된다. 

•  파라미터에 이전에 저장한 숫자또는 시작한 숫자를 1로 추가한다.
• 반복문에서 시작값을 이전에 저장한 숫자로 시작한다.
• 함수 재호출시 현재 반복문 되는 값으로 넣는다.    

Code

Python

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

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

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, depth + 1);
			}
		}
		
	}
		
}