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

하... 제가 미국 갔다 오고, 면접 준비 등 다양한(?) 일을 하느라

며칠 동안 코딩 테스트 준비를 제대로 하지 못했습니다.

그 결과, 다른 기업 코딩 테스트에서도 떨어지는 수모를 겪었습니다…

하지만! 다시 시작해야죠. (사실 내일도 코테가 있죠… 😇)

오늘 푼 문제는 백트래킹 N과 M 시리즈 중 세 번째 문제입니다.

이전에도 한 번 풀어봤지만, 기록은 오늘 남깁니다.

---

1. 문제: 백준 15651. N과 M (3)

• 단계: 🥈 실버 3단계
• 주제: 백트래킹
• 출처: https://www.acmicpc.net/problem/15651

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

---

2. 문제 풀이

해당 문제는 중복 순열을 구하는 문제입니다. 그렇기 때문에 기존의 순열 문제에 있는 조건문을 제거하면 됩니다.

구현 코드

def dup_permutations(N, M):
    ans = []

    def backtrack(curr):
        if len(curr) == M:
            ans.append(curr[:])
            return
        
        for i in range(1, N + 1):
            curr.append(i)
            backtrack(curr)
            curr.pop()
            
    backtrack([])

    return ans

def main():
    N, M = map(int, input().split())

    for perm in dup_permutations(N, M):
        print(*perm)

if __name__ == '__main__':
    main()

코드 설명

구성 요소 설명

backtrack(curr)	현재 수열 상태 curr에서 가능한 다음 숫자를 붙여가며 깊이 우선 탐색
for i in range(1, N + 1)	1부터 N까지 모든 숫자를 중복 포함 가능하게 순회
curr.append(i) → backtrack → curr.pop()	현재 숫자를 넣고 백트래킹, 끝나면 원상복구 (재귀 트리 구조)
중복 허용이므로 used[] 배열이 없음	중복을 막지 않기 때문에 별도의 방문 체크가 필요 없음

---

3. 마무리

이 문제는 중복 순열을 연습하기에 딱 좋은 문제였습니다.

특히 백트래킹에서 중복을 허용할 때는 방문 체크를 생략할 수 있다는 사실을 다시 한번 각인시켜줬습니다.

✨ 다시 달려보자.

실수와 멈춤은 있었지만, 기록은 남고 경험은 성장의 밑거름이 되니까요.

N과 M 시리즈 4번 문제로 이어갑니다.

중복 없이 오름차순 조합을 만드는 문제도 곧 업로드할 예정입니다! 💪

포기하지 않겠습니다.