[백준 문제 풀이] 15649번 N과 M (1)

Junu Kim·2026년 1월 20일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

89/89

[15649] N과 M (1)

난이도: ★★☆☆☆ • solved on: 2026-01-20

문제 요약

문제 유형: 백트래킹(Backtracking), 순열
요구사항: 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 모든 순열을 출력해야 한다.

사용 개념

자료구조
- int[] : 현재 선택된 수열을 저장
- boolean[] : 숫자 사용 여부(중복 방지) 체크
- StringBuilder : 출력 성능 최적화
알고리즘/기법
- 재귀 (recursion)
- 백트래킹 (backtracking)
핵심 키워드
- 순열 (permutation)
- 깊이 (depth)
- 상태 복원 (backtracking)

풀이 아이디어

1. 문제 분해

길이가 M인 수열을 만든다.

각 자리에 1부터 N까지의 숫자를 하나씩 시도한다.

이미 사용한 숫자는 다시 사용할 수 없다.

길이가 M이 되면 하나의 완성된 순열로 출력한다.

2. 재귀 함수의 목적 정의 (핵심)

sequence(n, depth)의 역할

depth == M
→ 길이 M의 수열이 완성되었으므로 출력하고 종료한다.

그렇지 않으면
→ 1부터 N까지 순회하면서 아직 사용하지 않은 숫자를 선택한다.

3. 핵심 로직 흐름
sequence(depth):
    if depth == M:
        수열 출력
        return

    for i = 1 to N:
        if i가 아직 사용되지 않았다면:
            i를 선택
            sequence(depth + 1)
            i 선택 취소 (상태 복원)
4. 백트래킹의 본질

선택: visited[i] = true, tempArr[depth] = i

재귀 호출: 다음 자리로 이동

복원: visited[i] = false

코드

import java.util.*;

class Main {
    public static int[] tempArr;
    public static boolean[] visited;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int r = sc.nextInt();

        tempArr = new int[r];
        visited = new boolean[n + 1];

        sequence(n, 0);
        System.out.println(sb);
    }

    public static void sequence(int n, int depth) {
        if (depth == tempArr.length) {
            for (int i = 0; i < tempArr.length; i++) {
                sb.append(tempArr[i]).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                tempArr[depth] = i;
                sequence(n, depth + 1);
                visited[i] = false; // 상태 복원
            }
        }
    }
}