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

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

15651번: N과 M (3)

이 문제는 백트래킹을 이용하는 문제로 실버 3문제입니다

---

해결책

문제는 간단합니다. 만약 n이  3이고 m이 2가 됬다면 2자리 수열로 모든 가능한 수를 만드는것입니다 .그러면 수열은 

(1,1),(1,2)......(3,3)까지 나오게 되는거죠. 이를 이용하면 다음과 같습니다

1. 해당 노드의 자리에 노드를 놓으면, 다음엔 자리수를 줄여서 재귀함수를 호출한다. 

예를 들어 n이 3이고 m이 2라고 했을떄, 맨 처음 자리에 수를 놨다면 그 다음에는 m-1를 해, 그 다음 자리수에 값을 집어 넣을 수 있도록 하는 것입니다. 

 

2. 만약 끝까지 갔다면 그 노드를 당장 출력하지 않고 문자열 변수에 저장한다.

보통 재귀함수의 종료조건까지 갔으면, 해당 수열을 출력하는 것이 맞다고 생각하실 수 있습니다. 하지만, 그렇게 된다면, 만약 m 과 n이 7 7이라면 경우의 수는 7^7이므로 굉장히 수가 길어집니다. 그 순간마다 출력을 요청하니, 시간이 오래걸리고, 시간초과가 날 것입니다. 그러므로 그 값을 출력이 아니라, 한 문자열 변수에 저장하며, 계속 단계를 진행하는것이 더 효율적입니다.

 

코드

---

import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	public static void main(String [] arg) {
		
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> list=new ArrayList<Integer>();
		int n=sc.nextInt();
		int m=sc.nextInt();
	    
		sol(n,m,list);
		System.out.println(sb);
	}
	public static void sol(int n, int m,ArrayList arr) {
		if(m==0) {
			int size=arr.size();
			
			for(int i=0;i<size;i++) {
				sb.append(arr.get(i)+" ");
				
			}
			sb.append("\n");
			return;
		}
		for(int i=1;i<=n; i++){
			arr.add(i);
			
			sol(n,m-1,arr);
			arr.remove(arr.size()-1);
			
			
		}
	}
}