For Programmer
백준 1311번 파이썬 문제풀이(할 일 정하기 ) - (dp + 비트마스킹) 본문
728x90
'''
| 특정 비트를 킬때 사용 ( 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))
728x90
'코팅테스트 > 백준 문제 모음' 카테고리의 다른 글
백준 2098번 파이썬 문제풀이(외판원 순회 ) - (dfs + 비트마스킹 + dp) (0) | 2022.04.17 |
---|---|
백준 1194번 파이썬 문제풀이(달이 차오른다 가자 ) - (dfs + 비트마스킹) (0) | 2022.04.15 |
백준 9252번 파이썬 문제풀이(LCS 2) - dp(역추적) (0) | 2022.04.13 |
백준 2096번 파이썬 문제풀이(내려가기) - dp (0) | 2022.04.12 |
백준 9251번 파이썬 문제풀이(LCS) - dp (0) | 2022.04.12 |
Comments