[백준] 15652번 : N과 M (4) (JAVA)

N과 M (1), (2), (3) 에 이어서, 드디어 N과 M의 시리즈 마지막 문제인 15652번 : N과 M (4)을 풀었다.

 

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

https://lucy1215.tistory.com/3

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

 

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

https://lucy1215.tistory.com/7

[백준] 15651번 : N과 M (3) (JAVA)

---

<문제>

<문제 해석>

백트래킹을 이용하여 1부터 N까지 M개의 수를 고른 수열을 출력하라.

-중복 가능

-비내림차순

 

 

<문제 해결>

앞의 문제인 N과 M (2), N과 M(3)를 섞어놓은 문제이다.

-현재 위치를 나타내는 location 변수를 추가한다.

 

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

 

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

 

3. 백트래킹 함수

 

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

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

 

                   ar의 index위치에 i 넣고,

                                     ↓

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

}
}

 

 

---

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

15652번: N과 M (4)