반응형
SMALL
10476 파이썬
-
10476번 좁은 미술관알고리즘 2023. 2. 13. 11:37
문제 설명 이번 문제는 가로로 두칸 세로로 N칸이 있는 미술관에서 각 방마다 가치가 정해져 있을 때, 아래 규칙대로 K개의 방을 닫아서 공개된 방의 가치의 합을 최대로 하는 경우를 구하는 문제입니다. 한쪽 끝의 두 방중 적어도 한 방에는 방문할 수 있어야 하고 다른 쪽 끝의 두 방중 한 방으로 나갈 수 있어야 한다. 즉, 같은 줄의 두 방을 모두 닫거나 대각선으로 붙어있는 두 방을 닫아서는 안 된다. 문제 풀이 아이디어 한 줄을 닫을 수 있는 방법의 수 한 줄에 있는 두 방을 모두 동시에 닫을 수 없으므로, 한 줄을 닫는 방법은 아래와 같습니다. 왼쪽만 닫는다 오른쪽만 닫는다 모두 열어 둔다 위와 같이 3가지 경우만 있습니다. 최대값을 구하는 방법 위에서부터 닫을 방을 정할 때, 현재 위치에서 각 방법에..