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

15649번 : N과 M (1), 15650번 : N과 M (2) 에 이어서, 바로 다음 문제인 15651번 : N과 M (3)을 풀었다.

 

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

https://lucy1215.tistory.com/3

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

 

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

https://lucy1215.tistory.com/5

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

---

<문제>

<문제 해석>

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

 

 

<문제 해결>

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

다만, 기존 문제는 중복 불가 였지만 이번 문제는 "중복 가능" 이라는 점의 차이가 있다.

 

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

 

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

 

3. 백트래킹 함수

 

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

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

 

                   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(0);
    	System.out.println(sb);
    
    	
    }
    
    public static void backtracking(int index) {
    	if(index == m) {
    		for(int i=0;i<m;i++) {
    			sb.append(a[i]).append(" ");
    		}
    		sb.append('\n');
    		return;
    	}
    	
    	for(int i=1;i<=n;i++) {
    		a[index] = i;
    		backtracking(index+1);
    	}
    }
    

}

 

 

---

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

15651번: N과 M (3)