42897

날짜: 2022년 1월 31일 오후 5:51

코드

원이 아니라 일직선일 경우는 DP로 쉽게 풀 수 있다는 사실을 알고 있었다.

그럼 이 문제를 일직선으로 변형할 수 있다면 쉽게 해결이 가능하다.

이를 하는 방법은 특정 한 집을 기준으로 털었을 경우아 털지 않은 경우로 나누어서 DP문제를 풀면된다.

털었을 경우에는 그 집의 좌우를 제외하고 DP문제로 풀면되고, 털지 않은경우는 이웃한 집을 포함해서 풀면된다. 그렇게 나온 결과 중 더 큰 값이 문제의 정답이 된다.