[APS] SWEA 9780. 외계인 침공 C++ 풀이 (DP)

 D5  https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXE0gpIa3dADFAVX&

SW Expert Academy

 

 

 Problem 

1. 개구리 나라에 N개의 도시(1 ≤ N ≤ 10⁶)가 1번부터 N번까지 순서대로 있고, 각각의 도시에는 Ai마리의 개구리(0 ≤ Ai ≤ 10⁹)가 살고 있다.

2. 한길이가 하루에 최대 한 도시, 오후에만 도시를 침공해서 개구리를 납치한다. 침공된 도시는 황폐화된다.

3. 침공된 도시의 개구리들은 모두 납치되지만, 그 다음 날 아침부터는 소식이 양 옆으로 점점 전파되고 그 도시에 있는 개구리들은 모두 방공호로 대피한다. (따라서 이후에 한길이가 도시를 침공해도 개구리를 납치할 수 없다.) 이때, 개구리가 살지 않는 마을에서는 소식 전파가 가능하지만, 이미 황폐화된 도시에서는 소식이 전파되지 않는다.

4. 한길이가 납치할 수 있는 개구리 수의 최댓값을 구한다.

 

 

 Solution 

제 나쁜 습관 중 하나는, 이런 문제를 보면 시간복잡도나 전체적인 알고리즘을 생각하지 않고 문제에서 쓰인대로 바로 구현하려고 한다는 점이에요😂 그래서 이 문제도 읽으면서 생각난 방법은 DFS, BFS 등이었고, 아무 생각없이 해당 방법으로 문제를 전개해나가려고 했는데… 아무리 생각해도 큰 N과 현실적으로 일일히 침공돼서 황폐화된 도시, 소식이 전파돼서 개구리가 대피한 도시, 아직 멀쩡한 도시 등을 고려하는 게 말이 안된다는 생각이 들더라구요. 완전탐색으로 풀면 당연히 시간초과 납니다.

그래서 도움을 좀 받았는데, 역시나 해결책은 DP였습니다. 입력값이 크다면 제발 DP나 이분 탐색을 생각하자. DP나 이분 탐색을 사용하는 문제는 문제만 봐서는 바로 해결책이 생각 안 나는 경우가 많은데, 이번 문제도 그런 것 같네요. 아직 제가 부족해서 그런거겠죠 ㅎ_ㅎ.. 풀이는 의외로 너무 간단해서 충격적. 문제 자체가 D5라기보다 문제를 읽고 DP를 생각해내는 게 D5인 것 같네요. 난 아직 멀었어..

해당 상황을 모두 구현하는게 포인트가 아니라, 결론적으로 1) 침공 당한 도시에서 인접한 도시는 침공될 수 없다. (적어도 한 칸 떨어져 있다.), 2) 결국 각각의 도시는 침공되고 안되고로 나뉜다. 이렇게 두가지가 포인트입니다. 즉, DP[i]의 기준을 "i번째 도시까지 침공했을 때 납치할 수 있는 개구리의 최댓값"으로 생각한다면, 상황은 복잡하지만 결국 DP[i-1]과 DP[i-2]+A[i] 중 더 큰 값을 D[i]에 넣어주고, D[N]이 정답이 되는 단순한 DP문제가 됩니다.

이때 주의해야 할 점은, 마을의 개수는 최대 10⁶개이고 한 마을의 개구리가 최대 10⁹마리이므로, 정답이 int의 범위를 넘어 long long이 된다는 것입니다. 해당 부분을 고려하지 않으면 당연히 어떤 경우는 맞고 어떤 경우는 틀리게 됩니다.

 

 

 Code