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

첫번째

import sys
sys.setrecursionlimit(int(1e8))
input = sys.stdin.readline

g = int(input())
p = int(input())
planes = []
for _ in range(p):
    planes.append(int(input()))
gates = {i:-1 for i in range(g)}
answer = []
def dfs(g, index, count):
    global answer
    if index == p - 1:
        answer.append(count)
        return

    for j in range(planes[index] - 1, -1, -1):
        if g[j] == -1:
            g[j] = index
            dfs(g, index + 1, count + 1)
            # g[j] = -1
            break
    else:
        answer.append(count)
        return

dfs(gates, 0, 0)
print(max(answer))

두번째

38%에서 시간초과 ㅜ0ㅜ

import sys
input = sys.stdin.readline

g = int(input())
p = int(input())
planes = []
for _ in range(p):
    planes.append(int(input()))
gates = [-1] * g
count = 0
for i, plane in enumerate(planes):
    for j in range(plane - 1, -1, -1):
        if gates[j] == -1:
            gates[j] = i
            count += 1
            break
    else:
        break
print(count)

검색해보니 분리 집합(유니온 파인드)으로 풀어야하는 문제라고 한다.
그래프 이론 공부한 후 다시 풀어보기로..