도둑질 (C++)

1d-1c/Programmers

yeon_11 2020. 4. 25. 16:27

코딩테스트 연습 - 도둑질

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한

programmers.co.kr

처음으로 알고리즘 문제를 풀었다.

** 생각해야될 조건

- 인접한 집은 도둑질이 안된다.

- 원 모양이므로, 첫 번째 집-마지막 집 = 인접하다

- i번째 집으로 생각해서 일반식을 만들어야함!

** 코드로 바꾼다면

1. dp[i] : i번째 집까지 털었을 때 최댓값

i-1번째 도둑질 O 경우 : i번째 집을 털 수 X -> dp[i-1]

i-1번째 도둑질 X 경우 : i번째 집을 털 수 O -> dp[i-2] + money[i]

그러므로 dp[i] = max( dp[i-1], dp[i-2]+money[i] )

2. 첫 번째 집 도둑질 O 경우 : n-2번째 집까지 털었을 때의 최댓값을 의미한다. (마지막 집(n-1번째 집)을 털 수 없기 때문에)

dp[0] = money[0]

dp[1] = money[0]

첫 번째 집 도둑질 X 경우 : n-1번째 집까지 털었을 때의 최댓값을 의미한다. (마지막집(n-1번째 집)을 털 수 있기 때문에)

dp[0] = 0

dp[1] = money[1]

백수연