[BOJ] 백준 1029번: 그림 교환

1일 1PS 15일차!

📚 문제

---

골드 1

• DP 와 비트마스킹을 사용한다.
• 이전에 가격을 위해 dp 에 [cost]까지 3차원 배열을 생성한다.

💡 포인트

---

1. dfs 를 돌면서 방문하지 않았고, 가격이 더 큰 경우에 cnt 를 추가한다.

💻 코드

---

n = int(input())
arr = []
for i in range(n):
    arr.append([int(j) for j in input()])

dp = [[[0] * 10 for _ in range(n)] for _ in range(1 << n)]


def dfs(now, artist, cost):
    if dp[now][artist][cost] != 0:
        return dp[now][artist][cost]

    cnt = 0
    for i in range(1, n):
        if arr[artist][i] >= cost and now & (1 << i) <= 0:
            cnt = max(cnt, 1 + dfs(now | (1 << i), i, arr[artist][i]))
    dp[now][artist][cost] = cnt

    return cnt


print(dfs(1, 0, 0) + 1)