[백준] 15650번 : N과 M (2) (JAVA)

앞에서 15649번 : N과 M (1)을 풀고 바로 다음 문제인 15650번 : N과 M (2)을 풀었다.

 

백트래킹에 대해 아직 이해하지 못했다면 다음의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/3

알고리즘 - 백트래킹(Backtracking)

 

바로 앞 문제인 15649번 : N과 M (1)에 대한 내용은 바로 앞의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/4

[백준] 15649번 : N과 M (1) (JAVA)

---

<문제>

 

<문제 해석>

백트래킹을 이용하여 1부터 N까지 중복 없이 M개의 수를 고른 오름차순 수열을 출력하라.

 

 

<문제 해결>

앞의 문제인 N과 M (1)과 비슷한 문제이다.

다만, 앞의 문제와 "오름차순" 이라는 조건이 추가가 되었다.

오름차순을 해결하기 위해서는 현재위치를 나타내기 위해 location이라는 변수도 추가해주었다.

 

1. n과 m을 입력받는다.

 

2. 탐색과정에서 값을 담을 int 배열 생성 : ar

 

3. 백트래킹 함수

 

 - index가 마지막 위치에 도달하면 수열을 출력하도록 한다.

 - for 문을 이용하여 수열 생성 (초기값 : location)

 

                   ar의 index위치에 i 넣고,

                                     ↓

      location값 1씩 증가, index값 1씩 증가하면서 재귀 진행

 

 

<코드>

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

class Main{
	static int n,m;
	static int a[];
	static StringBuilder sb = new StringBuilder();
	
    public static void main(String[] args) throws NumberFormatException, 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());
    	
    	a = new int[m];
    	
    	backtracking(1,0);
    	System.out.println(sb);
    
    	
    }
    
    public static void backtracking(int location, int index) {
    	if(index == m) {
    		for(int i=0;i<m;i++) {
    			sb.append(a[i]).append(" ");
    		}
    		sb.append('\n');
    		return;
    	}
    	
    	for(int i=location;i<=n;i++) {
    		a[index] = i;
    		backtracking(i+1,index+1);
    	}
    }
    

}

 

 

---

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)