[백준] 15649번 N과 M - JAVA

 

 

 

 

 

✍️풀이방식 

 

1. 문제 분석

 

• 1부터 N까지 자수 중에서 중복 없이 M개를 고른 수열
• 또한 수열은 사전 순으로 증가하는 순서, 즉 오름차순으로 정렬하여서 출력해야한다. 
• 현재 수열에서 추가할 수 있는 자연수를 탐색, 자연수가 기존 수열에서 이미 사용한 수라면 해당 수를 선택한 탐색은 진행하지 않고 이전 단계로 돌아간다(가지지치기) 
• 수열의 길이가 M이 될 때 수열의 정보를 출력한다 .

 

2. 풀이 과정 

 

일단 작은 수 부터 탐색하도록 기준을 잡으면 오름차순 조건을 자연스럽게 만족할 수 있다. 가지치기 기준은 이미 수열에 포함한 수(중복 허용 x) 

 

 

이전 단계로 돌아가는 로직은 재귀 함수 형태로 탐색하면 자연스럽게 구현된다. 

 

 

 

 

---

 

🖥️문제풀이

 

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


public class Main
{   
    static int N, M;
    static boolean[] V; //숫자 사용 여부 저장 배열 
    static int[] S;  // 수열을 담을 배열 
    
	public static void main(String[] args) throws IOException {
		
		Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
		S= new int[N];
		V= new boolean[N];
	    
	    backtracking(0); // 백트래킹 실행 (현재 포함된 수열 개수)
		
	}
	
	//백 트래킹 상세 구현 
    public static void backtracking(int length){
		    
		   if(length==M){ // 정답인지 확인해서 return 
		       printArray();
		       return;  // 정답 구현 
		   }                      
		                        
		   for(int i=0;i<N;i++){ // 탐색 기준 설정 
		       if(!V[i]){
		           V[i]=true; 
		           S[length]=i; 
		           backtracking(length+1);  // 재귀 호출 → 끝나면 돌아옴
		           V[i]=false; //다음 분기에서 사용할 수 있게 원상 복구  
		       }
		   }
		    
		}
		
	public static void printArray(){
	    
	    for(int i=0; i<M;i++){
	        System.out.print(S[i]+1+" "); 
	    }
	    
	    
	}	
	
}

 

 

• length = 현재까지 뽑은 원소 개수 (재귀 깊이)
• M = 뽑아야 하는 총 원소 개수 (목표 수열 길이)