BOJ 28241 - 교실 불 끄기
깡DP스러운 문제이고 헷갈리는것과 동시에 구현실수도 나서 오래 삽질했다.
공식 해설 의 사진이고 위와 같이 어떤 연속된 층계를 이동하는데는 총 $4$가지가 있음을 확인하고 DP를 정의한다.
$dp[i][j]=i$ 번째층과 $i+1$번째 층을 $j$번째 타입으로 이동할 때 $1 \sim i$ 층까지 모두 끄는데 최소 이동횟수
항상 $x=0$ 에서 시작하므로 $dp[0][0]=dp[0][1]=0$ 으로 초기화하고, (지하 1층에서 1층으로 올라온다고 생각하면 된다.) $dp[0][2]=dp[0][3]= \infty$로 초기화한다.
이제 공식 해설에 있는 점화식을 적용하면 되는데, 눈여겨볼것은 무조건 한 줄을 거쳐가야 하는 $m+1$이 소모되는 경우의 수들 말고, 왼쪽 오른쪽을 모두 거치기 때문에 그리디하게 좌우로 끌 수 있는 경우 층에 있는 전구들의 위치에 $0$과 $m+1$을 추가해줘서 인접한 위치들의 가장 큰 차이만큼은 이동하는 경로에 포함을 시켜주지 않아도 된다는 점이고, 그것이 최적이라는 점이다.
Comments