[백준] 15651 N과 M (3) - Java

 

 

 

완전탐색 문제이다. 

 

for문을 적당히 사용하면 쉽게 해결할 수 있지만, 답을 구하는 함수와 메인 함수를 구분해서 코드를 작성하고, 답을 구할 때 재귀를 사용해 좀 더 효율적으로 풀어보자.

 

 

Java

 

 

 

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

public class Main {

	static int N;
	static int M;
	static StringBuilder sb = new StringBuilder();
	static int[] selected;

	public static void main(String[] args) throws 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());
		selected = new int[M+1];

		sol(1); // 탐색은 1부터 진행함
		System.out.println(sb);
	}

	static void sol(int k){

		if(k == M+1){  // 다 골랐을 경우. 출력해주자.
			for(int i=1; i<M+1; i++){
				sb.append(selected[i]).append(" ");
			}
			sb.append("\n");
		}else{ // 아직 다 고르지 못함. 값을 넣어 보고 다음 함수 호출
			for(int i=1; i<N+1; i++){
				selected[k] = i; 
				sol(k+1); // k+1 부터 M까지 탐색은 재귀로 처리함
				selected[k] = 0;
			}
		}
	}
}

 

 

재귀를 사용해서 풀면 코드가 훨씬 깔끔해지지만.. 재귀에 익숙하지 않으면 사용하기 어렵다. 많이 연습해서 익숙해지자.

 

풀이 로직을 이해하고 반복해서 공부하자.