[백준] 5721 사탕 줍기 대회

문제소개

---

5721 사탕 줍기 대회 복잡한 부분을 어떻게 하면 간단하게 정리할 수 있을까를 생각하는게 중요한 것 같습니다.

아래 그림과 같이 3 X 3 칸에서 11개의 사탕을 줍는다면 윗 줄,아랫 줄, 좌, 우의 사탕은 먹지 못합니다. 

못 먹는 사탕을 0으로 바꾸는 작업을 하게 된다면.. 문제는 미궁 속으로 빠집니다. 

이러한 복잡한 부분을 어떻게 간단하게 바꿀 수 있을까요?

 

 

 

 

 

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

 

 

 

문제풀이

 

---

 

 

 

 

 

1	8	2	1	9
1	7	3	5	2
1	2	10	3	10
8	4	7	9	1
7	1	3	1	6

 

 

 

 

 

다음과 같은 그림이 있습니다. 3 X 3 칸에서 10개의 사탕을 줍는다면 윗 줄, 아랫 줄은 못 먹습니다. 그러나 3 X 3이 속한 3행의 1, 10은 먹을 수 있습니다. 그럼 선택한 행에서는 최대한 많이 사탕을 줍는 것이 현명합니다. 

→ 각 행에서 가장 많이 사탕을 줍는 개수로 정리할 수 있으며 간단한 DP로 해결할 수 있습니다.

1

...

i-2

i-1

i

 

 

DP[i] = 1부터 i 번까지 주운 최대 사탕 

DP[i] = max(DP[i-1], DP[i-2] + i 번째 사탕)

 

 

1	8	2	1	9				17
1	7	3	5	2				12
1	2	10	3	10		▷		21
8	4	7	9	1				17
7	1	3	1	6				16

 

다음과 같이 간단하게 정리 할 수 있으며 

한 행에서 주운 최대 사탕 개수와 동일한 방법으로

한 열에서 주운 최대 사탕 개수로 해결할 수 있습니다.

 

---

소스보기