백준 15649번: N과 M

백준 15649번: N과 M(1)
백준 15650번: N과 M(2)
백준 15651번: N과 M(3)
백준 15652번: N과 M(4)
백준 15654번: N과 M(5)
백준 15655번: N과 M(6)
백준 15656번: N과 M(7)
백준 15657번: N과 M(8)
백준 15663번: N과 M(9)
백준 15664번: N과 M(10)
백준 15665번: N과 M(11)
백준 15666번: N과 M(12)

백트래킹 문제이다. 조건에 맞는 경우만 탐색하고 조건에 맞지 않는 경우(이미 방문한 원소이거나, 오름차순이 아니거나)는 탐색하지 않는다.
지금까지 만든 수열을 seq에 저장하고 길이가 M이 되었을 때 출력한다.
1번, 2번 문제만 풀면 나머지는 쉽게 풀 수 있다.

1. 이미 방문한 원소에 대해 탐색하지 않는 방법

seq에 원소를 삽입, 삭제할 때 visited를 업데이트 해 준다.

2. 오름차순이 되도록 탐색하는 방법

seq의 마지막 원소와 현재 탐색하려고 하는 원소를 비교한다.

3번, 4번 문제는 지금까지 걸어놓은 조건을 적절히 제거하면 풀 수 있다.

5번부터는 N개의 서로 다른 자연수를 직접 입력받고
9번부터는 N개의 자연수를 직접 입력받는다(중복 가능)

모든 조건이 걸려있는 10번 문제의 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
numList = list(map(int, input().split()))
numList.sort()

visited = [False]*N
seq = []
seqset = set()


def solve(visited, seq, count):
    if count == 0:
        tSeq = tuple(seq)
        if tSeq not in seqset:
            for i in seq:
                print(i, end=' ')
            print()
            seqset.add(tSeq)

    else:
        for i in range(N):

            if visited[i] is True:
                continue

            if seq:
                if numList[i] < seq[-1]:
                    continue

            visited[i] = True
            seq.append(numList[i])
            solve(visited, seq, count - 1)
            visited[i] = False
            seq.pop()


solve(visited, seq, M)

오름차순으로 출력하기 위해 입력받은 자연수들을 sort한다.
중복되는 수열을 출력하지 않기 위해 seqset에 지금까지 출력했던 수열을 저장한다. list는 unhashable 하기 때문에 튜플로 바꿔서 set에 추가한다.

여담

오늘 12문제나 풀어서 백준 골드가 되어버렸다. 상병이 되기 전에 골드 찍기가 목표였는데 아직 일꺾도 안됐다. 시간이 너무 많다 못해 흘러 넘친다. 다음 목표는 플레티넘이다.