99클럽 코테 스터디 21일차 TIL - 42897 도둑질

42897. 도둑질 / c++ / level4 / 1시간+

문제 및 코드

접근 방식

동적 계획법

1. 이런 식의 문제는 보통, 현재 칸에서 행동함 = 전 칸의 행동 안한 결과 + 현재 칸의 값 으로 풀 수 있다.
2. 다만 이 문제의 경우 순환 배열이어서 시작 원소와 마지막 원소 역시 위의 조건을 만족해야 했다.
3. 고민 끝에 내가 생각한 방법은, 배열을 아래처럼 총 4개 만들어주는 것이었다.
   1. 현재 집을 도둑질 함 (시작 지점을 도둑질한 경우)
   2. 현재 집을 도둑질 하지 않음 (시작 지점을 도둑질한 경우)
   3. 현재 집을 도둑질 함 (시작 지점을 도둑질하지 않은 경우)
   4. 현재 집을 도둑질 하지 않음 (시작 지점을 도둑질하지 않은 경우)
4. 이렇게 한 뒤, 맨 마지막 집 전까지만, 배열을 순회하며 dp값을 저장해주고,
   맨 마지막 집의 경우 3-3번에만 값을 더 해주었다. (3-1의 경우 시작 지점을 도둑질 했기 때문에 마지막 집을 도둑질할 수 없다.)
5. 그 후, 나온 값들 중 가장 큰 값을 비교하여 반환

생각해 볼 점

1. 확실히 level4 문제들은 난이도가 있다고 생각이 들었다.
2. 다만 이 문제의 경우 이전에도 접해본 dp문제 유형이었는데, 거기에 시작 지점의 값도 추가로 신경써줘야하는 응용 문제여서 생각만 잘 했다면 충분히 빨리 풀 수 있었는데, 이건 좀 더 반복적으로 연습을 해야겠다.

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL