[JAVA] 백준 15560 N과M (4)_백트래킹

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

15652번: N과 M (4)

 

 접근 : 

 

 - N 과 M 을 입력 받는다.

 

 - 이전의 숫자를 보유(now)한다.

 

 - Depth 를 내려갈 때, 이전의 숫자(now) 부터 수를 증가시킨다.

 

  * 비오름차순을 제외한 코드에서 for 루프를 돌 때, 위의 조건만 추가하면 된다.

 

https://kjwit.tistory.com/entry/JAVA-%EB%B0%B1%EC%A4%80-15651-N%EA%B3%BC-M-3%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9 

[JAVA] 백준 15651 N과 M (3)_백트래킹

 

 

코드구현 : 

 

import java.io.*;

public class Main {
	static class Dfs {
		private int n;
		private int m;
		private int[] visited;
		private StringBuilder result;

		public Dfs(int n, int m) {
			this.n = n;
			this.m = m;
			this.visited = new int[n + 1];
			this.result = new StringBuilder();
		}

		void doDfs(int depth, int now) {
			if (depth == m) {
				for (int i = 0; i < m; i++) {
					result.append(visited[i]).append(" ");
				}
				result.append("\n");
				return;
			}
			for (int j = now; j <= n; j++) {
				visited[depth] = j;
				doDfs(depth + 1, j);
			}
		}

		String getResult() {
			return result.toString();
		}
	}

	public static void main(String[] srgs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inputs = br.readLine().split(" ");
		int n = Integer.parseInt(inputs[0]);
		int m = Integer.parseInt(inputs[1]);

		Dfs dfs = new Dfs(n, m);
		dfs.doDfs(0,1);

		System.out.println(dfs.getResult());
	}
}

 

 

 - 이너 클래스 사용 X

 

import java.io.*;
public class Main {
    private static int n;
    private static int m;
    private static int[] selected;
    private static StringBuilder sb;

    static void input() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        n = Integer.parseInt(inputs[0]);
        m = Integer.parseInt(inputs[1]);
        selected = new int[m];
        br.close();
    }

    static void recFunc(int k, int now){
        if(k == m + 1) {
            for (int i : selected) {
                sb.append(i).append(' ');
            }
            sb.append('\n');
            return;
        }
        
        for(int i = now ; i <= n ; i++){
            selected[k-1] = i;
            recFunc(k+1, i);
        }
    }

	public static void main(String[] args) throws IOException {
        sb = new StringBuilder();
        input();
        recFunc(1, 1);
        System.out.println(sb);
	}
}