1. 공부한 내용

문제1 - 99 클럽 - 도둑질:

[ 문제 풀이 ]

문제는 위와 같이 원형 꼴로 집이 배치되어 있을 때, 연속된 2개 이상의 집을 터는 경우를 제외하고 집을 털 경우, 가장 많이 획득할 수 있는 돈을 return 하는 문제이다. 주어진 범위가 크고 반복적으로 확인할 필요 없이, 앞선 2개의 값만 확인해서 비교하면 되기 때문에 dp로 접근하여 풀이하는 문제이다.

⇒ 이 문제의 가장 핵심은 첫 번째 값과 마지막 값이 연결되어 있기 때문에 여기에 대한 판단을 추가로 해야 하는 것이다.

나는 다음과 같은 방식으로 접근하였다.

1. 1 번째 값을 포함하는지 여부에 따른 결과

2. reverse하여 진행하고, 똑같이 1 번째 값을 포함하는지 여부에 따른 결과

3. max 값을 먼저 도출하여 이를 시작 값으로 하여 판단하기

⇒ 하지만, 풀이가 지저분해졌고 풀이 도중 도저히 효과적인 방법이 떠오르지 않아 다른 사람의 풀이를 참고하였다.

다른 사람의 풀이는 나와 비슷하였으나 dp를 무조건 2개 채택하였고 다음과 같았다.

1. 첫 집을 무조건 털기

dp1 = [0] * len(money)
dp1[0] = money[0]
dp1[1] = max(money[0], money[1])

for i in range(2, len(money)-1): # 첫 집을 무조건 터는 경우
    dp1[i] = max(dp1[i-1], money[i]+dp1[i-2])

2) 마지막 집을 무조건 털기 ⇒ 가장 핵심!!!!!!!!!!!!!!

dp2 = [0] * len(money)
dp2[0] = 0
dp2[1] = money[1]

for i in range(2, len(money)): # 마지막 집을 무조건 터는 경우
    dp2[i] = max(dp2[i-1], money[i]+dp2[i-2])