[JAVA] 백준 15650 N과M(2)_백트래킹

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

15650번: N과 M (2)

 

 접근 : 

 

 - n 과 m 을 입력 받는다.

 

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

 

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

 

  * 비오름차순을  코드에서, 위의 조건만 추가하면 된다.

 

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

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

 

코드 구현 : 

 

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+1);
			}
		}

		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+1];
        sb = new StringBuilder();
        br.close();
    }

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

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