[BOJ] 백준 15650번: N과 M (2)_자바(JAVA)

1. 문제

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

15650번: N과 M (2)

---

2. 접근 및 해결

2-1) 접근

1. 백트래킹으로 해결

2.  중복 없이 M개를 고른 수열 +  오름차순 -> 현재 나온 숫자가 다음에 나올 숫자보다 크면 출력하지 않음

 

2-2) 해결

if(cnt==M) {
    StringBuilder sb2 = new StringBuilder();
    for(int i=0; i<M; i++) {
        if(((i+1)!=M) && list[i]>list[i+1]) return; // 이 코드를 빼면 15649번 풀이와 같아짐
        sb2.append(list[i] +" "); 
    }
    sb.append(sb2.toString() + "\n");
    return;
}

cnt가 M과 같다는 것은 출력해야하는 최종 잎(leaf node)에 도달했다는 것입니다. 

따라서 출력을 하되, 접근 2에서 말했듯이 현재 나온 숫자가 다음에 나올 숫자보다 크면 출력하지 않는 if문을 작성해줍니다.

핵심 백트래킹 코드는 아래와 같습니다.

for(int i=1; i<=N; i++) {
    if(!isUsed[i]) { 
        list[cnt] = i;
        isUsed[i] = true;
        print(cnt+1); 
        isUsed[i] = false;
    }
}

list[cnt] 값은 백트래킹이 실행되면서 계속 덮여지는 숫자이기 때문에 재귀 이후 굳이 초기화해주지 않았습니다.

isUsed 배열로 현재 사용된 숫자를 확인합니다. 

---

3. 코드(JAVA) 

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

public class Main {
	static int N, M;
	static int[] list;
	static boolean[] isUsed;
	static StringBuilder sb;
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		sb = new StringBuilder();
		list = new int[N];
		isUsed = new boolean[N+1];
		print(0);
		
		bw.write(sb.toString());
		br.close();
		bw.close();
	}
	
	public static void print(int cnt) {
		if(cnt==M) {
			StringBuilder sb2 = new StringBuilder();
			for(int i=0; i<M; i++) {
				if(((i+1)!=M) && list[i]>list[i+1]) return;
				sb2.append(list[i] +" "); 
			}
			sb.append(sb2.toString() + "\n");
			return;
		}
		
		for(int i=1; i<=N; i++) {
			if(!isUsed[i]) { 
				list[cnt] = i;
				isUsed[i] = true;
				print(cnt+1); 
				isUsed[i] = false;
			}
		}
	}
	
}

 

* 참고한 블로그

 

https://kimtaesoo99.tistory.com/18

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