링크
도둑질
난이도
- 프로그래머스에서는 4지만 쉬운편이다.
- 기본 다이나믹으로 보임
문제요약
- 원형태로 이어진 집들을 도둑질을 하려고한다. 연속된집을 털면 경보가 울리게되어있다(2번집 털면 1번집과 3번집은 못턴다)
- 최대로 도둑질해서 얻는 금액은?
해결법
- 그냥 한칸씩 띄어서 보면 된는 문제가 아니라 좀더 생각해봐야한다.
- [4 4 10 4 4 10]가 있을때, 1번집부터 털면 18, 2번집부터 털면 18이 나온다. 하지만 눈으로 봐도 알듯이 최대는 20이다.(맨앞과 맨뒤는 연결되어있다고 보고 생각해야한다.)
- 다이나믹으로 i위치에 있을때 최대로 얻을수 있는 금액을 계산해가면서 진행해야한다.
- 다이나믹도 두가지 경우로 나눠서 생각해야한다.
- 맨앞 위치를 무조건 먹었을경우
- 맨앞을 뛰고 시작했을경우
- 위와 같은 두가지 경우를 생각하는 이유는
맨앞과 맨뒤가 연결되어있기때문이다.
- 맨앞을 먹었으면 맨뒤는 포함하지않아야하며, 맨앞을 건너뛰었으면 맨뒤를 먹을 가능성이 생기기 때문이다.
간단 알고리즘
- 기본
- money - 집마다 가지고있는 돈들
- result = [money복사] # 두개 필요 맨앞먹었을때, 맨앞을건너뛰었을때
- 맨앞을 무조건 먹었을경우
- i==0 result[i] = result[i]
- i==1 result[i] = 0
- i==2 result[i] = result[i-2]+result[i]
- i>=3 result[i] = result[i-2]과 result[i-3]을 비교하여 큰것을 result[i]와 더함
- 마지막
- result[맨뒤-1]와 result[맨뒤-2]를 비교하여 큰것을 저장
- 맨앞을 건너띄고 먹었을경우
- i==0 result[i] = 0
- i==1 result[i] = result[i]
- i==2 result[i] = result[i]
- i==3 result[i] = result[i-2]+result[i]
- i>=4 result[i] = reuslt[i-2]와 result[i-3]을 비교하여 큰것을 reulst[i]와 더함
- 마지막
- 맨마지막을 먹어도 되기때문에 result[맨뒤]와 result[맨뒤-1]를 비교하여 큰것 저장
맨앞 무조건 먹엇을때의 큰것을 같이 비교하여 큰것을 최종적으로 출력
후기
- 다이나믹 프로그래밍의 기초지식을 알고있으면 풀수있는 문제라고 생각
- 문제를 세분화해서 반복되는 부분을 확인하고 적용
- 원 형태라는조건이 머리가 좀 아픔