1017: 돈을 줍자

Link : judge.koreatech.ac.kr/problem.php?id=1017

---

1. 문제

• 동수가 길을 걷고 있는데, 천사가 나타나서 가는 길에 돈을 뿌려 놓았다. 그리고는 하는 말이
  
  "마음껏 돈을 가져가세요, 하지만 연속해서 3개의 돈을 주우면 지옥에 가게 됩니다"
  
  불쌍한 동수를 위해 가장 많은 돈을 주울 수 있는 프로그램을 작성해서 건내주도록 합시다.
  돈이 [5, 7, 10, 1, 2, 10, 11, 6] 으로 놓여져 있다면  [5, 7, 10, 1, 2, 10, 11, 6]  이렇게 7, 10, 10, 11을 주어 38원(.....) 을 주울 수 있습니다.

 

---

2. 문제의 조건

• 1 <= N <= 1,000 (N : 떨어진 돈의 갯수)

 

---

3. 문제 접근

• 시간 복잡도
  
  시간제한이 1초에 N이 1000개 이하니 O(N^2.666) 이내의 시간에 풀면 되겠다고 생각하였습니다.

 

• 아이디어
  
  해당 문제는 DP의 전형적인 유형이라고 합니다.
  현재 풀이에서 저는 dp를 "과거" 중 최선을 방법을 선택한 기록(?)들이라고 생각합니다.
  5 7 10 1 2 10 11 6 이있을때
  i = 1일 때는 5를 줍는게 최선이고
  i = 2일 때는 5, 7을 줍는게 최선이고
  i = 3일 때에는 7, 10을 줍는게 최선입니다. 즉 dp = [5, 12, 17]로 작성이 됩니다.
  케이스는 2가지입니다.
  1. 3칸전의 최대로 주운 돈 + (과거[-1]~현재)
     [1 0 1 1] "1"은 동전을 줍는 케이스
  
  2. 2칸전의 최대로 주운 돈 + 현재
     [1 1 0 1] 이 두개로 나누어집니다!
  
  

 

 

---

4. 풀이 방법

• dp[0]은 arr[0]번째이다
• dp[1]은 arr[0] + arr[1]이다.
• dp[1]은 dp[0] vs dp[1] vs arr[1] + arr[2] 중 가장 큰 값이다.
• [1 0 1 1] 형태를 줍는 점화식은 dp[i - 3] + arr[i - 1] + arr[i]
  [1 1 0 1] 형태를 줍는 점화식은 dp[i - 2] + arr[i] (dp[i-2]는 그 이전 동전을 줍는 최선의 방법임.)
• [1 0 1 1], [1 1 0 1] 방식 중 가장 큰값이 dp[i]가 됨.

 

---

5. 소스코드

• cjw-git.tistory.com/24

 

---

 

cjw.git@gmail.com