백준 15652번 : N과 M (4) (Java)

🔗 문제 링크

15652번: N과 M (4)

---

📖 풀이 과정

 

- 재귀 유형의 문제입니다.
- 15650번 문제의 조건문에서 이전의 값(마지막에 배열에 할당한 값)과 지금 넣을 값이 같을 경우를 고려해야 합니다.
- 저는 단순히 이 두가지에 대한 조건문을 명시해서 구현했습니다.
- 추후, 좀 더 간단하게 작성을 해보겠습니다.

 

---

💻 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
 static int n,m;
 static int[] arr;
 static boolean[] visited;
 
 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());
  visited = new boolean[n + 1];
  arr = new int[m];
  
  solve(0);
 }
 
 public static void solve(int idx){
  if(idx == m){
   for(int i = 0; i< m; i++){
    System.out.print(arr[i] + " ");
   }
   System.out.println();
   return;
  }
  
  for(int i = 1; i<= n; i++){
   if(visited[i] && arr[idx - 1] == i){
    visited[i] = true;
    arr[idx] = i;
    solve(idx + 1);
    visited[i] = false;
   }
   else if(!visited[i]){
    if(idx == 0 || arr[idx - 1] < i){
     visited[i] = true;
     arr[idx] = i;
     solve(idx + 1);
     visited[i] = false;
    }
   }
  }
 }
}