[백준] 15650번 N과 M(2) JAVA (자바) 풀이

문제 15650번 (백트래킹)

 

 :  자연수 N과 M이 주어졌을 때,
    1부터 N까지 자연수 중에서 중복 없이 M개를 골라서 수열 구하기

 

 :  고른 수열은 오름차순

   

    (예) N = 3, M = 2 인 경우

    1~3까지의 수 중에서 1개만 골라서 만들 수 있는 수열을 모두 만든다

    1, 2 / 1, 3 / 2, 3 이렇게 만든 수열을 한줄에 하나씩 출력한다

 

 

 [입력]

 :  첫 줄에 자연수 N, M (1 ≤ M ≤ N ≤ 8)

 [출력]

 : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력 (중복 수열 X)

   수열의 원소는 공백으로 구분해서 출력

 

 : 수열은 사전 순으로 증가하는 순서로 출력

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹

 

 문제 조건 1) 숫자 중복금지 
 문제 조건 2) 수열 원소 오름차순 

 

 종료 조건) 배열이 M만큼 채워지면 출력하고 boolean false

 

 N과 M(1) 문제와 다르게 boolean이 필요없다

 현재 숫자보다 무조건 다음 인덱스의 숫자가 커져야 하기 때문에

 현재 숫자 + 1을 백트래킹에 넣어서 돌리고 for문 시작지점을 조정하면 된다

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N,M;
    static int arr[];
    static StringBuilder sb = new StringBuilder();
    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());
        arr = new int[M];
        back(0, 1);
        System.out.println(sb);        
    }
    
    public static void back(int depth, int next){
        if(depth==M){
            for(int j : arr){
                sb.append(j).append(" ");
            }
            sb.append('\n');
			return;
        }
        
        for(int i=next; i<=N; i++){
            arr[depth] = i;
            back(depth+1,i+1);
        }   
    }
}

 

 

 [해설]
     

 : static int N, M;  첫째줄 입력
   static int arr[];  수열
   static StringBuilder sb = new StringBuilder();  몰아서 출력하기
  

  : StringTokenizer st = new StringTokenizer(br.readLine());  끊어읽기
    N = Integer.parseInt(st.nextToken());  수열 원소 개수
    M = Integer.parseInt(st.nextToken());  새로 만들 수열 원소 개수
    arr = new int[M];  새로 만들 수열 배열
      
  : back(0, 1);  깊이, 그다음 배열의 숫자
 

  : System.out.println(sb);  출력    
    
    
  : public static void back(int depth, int next){  
        if( depth == M){  M만큼 돌면 종료하고 수열 출력
            for(int j:arr){
                sb.append(j).append(" ");  수열배열 
            }
            sb.append('\n'); 개행
            return;
            
        }
        
        for(int i = next; i<=N; i++){  
           arr[depth] = i;  출력할 숫자 추가
           back(depth + 1, i + 1);  다음 층 (다음 인덱스) 백트래킹 반복, 그 다음 숫자 추가
        }
    }
  

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *