BOJ 백준 15664: N과 M (10)

Table of contents

들어가며

이 문제는 전형적인 백트래킹 문제입니다.
그래서 빨리 풀려고 했는데, 자꾸 3%에서 WA 떠서 문제를 어디서 잘못 읽었나 곰곰이 생각하고, 문제지도 다시 읽었습니다.

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

이 부분이 문제였습니다.
예를 들어 아래 input에 대해서

3 2
1 9 10

1 9
1 10
9 10

이 나와야 하는데, 저는 계속

1 10
1 9
9 10

이 나오게 했었습니다.
즉, 문자열 기준 사전식 나열을 하고 있었던 것입니다.

AC 받은 Python 코드

import sys

input = sys.stdin.readline


def combination(cur_len, cur_idx):
    # base condition 1
    if cur_len == M:
        ans.add(tuple(seq))
        return

    for i in range(cur_idx + 1, len(nums)):
        if isUsed[i]:
            continue
        isUsed[i] = True
        seq.append(nums[i])
        combination(cur_len + 1, i)
        isUsed[i] = False
        seq.pop()


if __name__ == "__main__":
    N, M = map(int, input().rstrip().split())
    nums = [*sorted(map(int, input().rstrip().split()))]
    seq = []
    ans = set()
    isUsed = [False for _ in range(len(nums))]
    # NCM 결과 출력 (단, 단조 증가 수열)
    for i in range(len(nums)):
        isUsed[i] = True
        seq.append(nums[i])
        combination(1, i)
        seq.pop()
        isUsed[i] = False
    for s in sorted(ans):
        print(" ".join(map(str, s)))