백준 15652번 - N과 M (4) 자바 풀이

문제 링크

문제 풀이 시간 : 15분

문제 요약

주어진 n과 m에 대해 1부터 n까지의 수로 이루어진 비내림차순 수열을 구하는 문제
수열은 m개의 숫자로 이루어져 있고, 같은 수를 여러 번 고를 수 있음
수열은 비내림차순이어야 하며, 사전 순으로 출력해야 함

문제 풀이

이 문제는 백트래킹 기법을 사용하면 해결할 수 있다.

접근 방법

n개의 숫자 중에서 m개의 숫자를 선택하는 문제인데, 각 숫자는 이전 숫자보다 크거나 같은 숫자여야 한다.
비내림차순 조건을 만족시키기 위해 재귀적으로 이전 수보다 크거나 같은 수를 고르면 된다.
중복이 허용되므로, 수열을 생성하는 동안 중복된 수가 나오지 않도록 주의할 필요는 없지만, 비내림차순 조건이므로 이전 숫자부터 고르게 된다.

백트래킹 설명

arr 배열을 만들어 m개의 숫자를 저장한다.
find(idx, a) 함수는 arr[idx]에 값을 할당하고, 그 값이 a 이상이어야 한다. 이때 a는 이전에 고른 숫자다.
idx == m이면, arr 배열이 완성된 상태이므로 해당 배열을 출력한다.
재귀적으로 진행하면서 중복된 값을 허용하지만, 비내림차순 조건을 만족하기 위해 이전 값부터 선택할 수 있도록 한다.

최종 코드

java

import java.io.*;
import java.util.*;

public class Main {
	public static int[] arr;
	public static int n,m;
	public static StringBuilder sb = new StringBuilder();
	
	public static void find(int idx, int a) {
		if(idx == m) {
			for(int num : arr) {
				sb.append(num).append(" ");
			}
			sb.append("\n");
			return;
		}
		
		for(int i=a;i<=n;i++) {
			arr[idx] = i;
			find(idx+1, i);
		}
	}
	
	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());
		
		arr = new int[m];
		find(0,1);
		
		System.out.println(sb.toString());
	}
}

15652번 - N과 M (4)

문제 풀이 시간 : 15분

문제 요약

문제 풀이

접근 방법

백트래킹 설명

최종 코드

함께 읽으면 좋은 글

5430번 - AC

1966번 - 프린터 큐

1158 - 요세푸스 문제

2164번 - 카드2