백준 1311번 파이썬 문제풀이(할 일 정하기 ) - (dp + 비트마스킹)

---

'''
| 특정 비트를 킬때 사용 ( x |= (1 << 2))
& 특정비트가 켜져있는지 혹은 특정 비트를 끌 때 사용 (x & (1 << 2)) != 0 or (x & ~(1 << 2)
^ 특정 비트 상태를 반전시킬 때 사용 (x ^ (1 << 2))
tip) x & (-x) x의 제일 오른쪽 1이 나온다.
'''

import sys

input = sys.stdin.readline


def dfs(row, visit):
    if row == N:
        return 0

    if visited[row][visit] != -1:
        return visited[row][visit]

    ret = 1000000000
    for i in range(N):
        if (visit & (1 << i)) != 0:  # 특정 비트가 켜저있다면
            continue

        ret = min(ret, dfs(row + 1, (visit | (1 << i))) + tasks[row][i])

    visited[row][visit] = ret

    return visited[row][visit]


N = int(input())
tasks = [list(map(int, input().split())) for _ in range(N)]

visited = [[-1] * (1 << N) for _ in range(N)]
print(dfs(0, 0))

-> 위와 같이 2차원 방문처리로 풀어도 되고 시간복잡도를 더줄이고 싶다면 아래와 같이 1차원 방문처리로 풀어도 상관없다.

 

import sys

input = sys.stdin.readline


def dfs(row, visit):
    if row == N:
        return 0

    if visited[visit] != -1:
        return visited[visit]

    ret = 1000000000
    for i in range(N):
        if (visit & (1 << i)) != 0:  # 특정 비트가 켜저있다면
            continue

        ret = min(ret, dfs(row + 1, (visit | (1 << i))) + tasks[row][i])
       
    visited[visit] = ret

    return visited[visit]


N = int(input())
tasks = [list(map(int, input().split())) for _ in range(N)]

visited = [-1] * (1 << N)
print(dfs(0, 0))