백준 15652 N과 M (4) 자바 풀이

난이도 : 실버3

풀이일 : 2401276

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

15652번: N과 M (4)

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import java.util.Scanner;

public class Main {
	static int N, M;
	static int[] array;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		array = new int[M];
		
		DFS(0, 0);
		System.out.print(sb);
	}
	
	static void DFS(int depth, int num) {
		if (depth == M) {
			for (int i : array) {
				sb.append(i+ " ");
			}
			sb.append('\n');
			return;
		}
		for (int i = num; i < N; i++) {
			array[depth] = i + 1;
			DFS(depth + 1, i);
		}
	}
}

• 입력 받을 값이 적어 Scanner 사용
• N, M 의 값을 입력 받고, M 크기의 array를 만들어 준 후 DFS 탐색
• 중복되는 숫자를 다시 출력해도 괜찮으므로, 방문 확인용 visited 배열을 미생성
• 숫자는 오름차순으로 증가해야 한다는 조건이 추가되었으므로, DFS 인자로 num 추가
  • 반복문 조건을 num부터 시작해 N까지로 설정
• 최종적으로 StringBuilder에 담긴 것들 출력

---

느낀점

• 도시 이동 버스에서 급하게 풀어 남기는 오늘의 알고리즘. 매일 올리기 시작한게 얼마나 됐다고 어제 컨디션 이슈로 못올린게 그렇게 아깝다. 미리 미리 풀어서 시간 여유 넘치게 올려야지 앞으로는