백준온라인 1006번 [습격자 초라기] [C++]

www.acmicpc.net/problem/1006

1006번: 습격자 초라기

---

문제 요약

1.길이가 N인 원형큐 2개가 인접하게 붙어있다

2.특수소대가 비용이 w보다 작게끔 하나또는 두개의  구역을 침투시킨다고 할때

3.가능한 최소의 파견 소대의 수를 출력

 

---

나의 풀이

DP문제라는것을 안 상태에서 문제를 풀었음에도 난이도가 상당했다

 

처음 원형큐를 잘라서

1 2 .......... N

1 2 ...........N 이렇게 입력으로 주어진 그대로 생각해보면 힌트를 얻을수 있다

 

입력으로 주어진 배열을 D배열이라고 하고  \(D[N+1][2]\) 선언이 필요!

내가 최소의 파견횟수를 알아낼수 있는 배열을 DP배열 이라고 하자  \(DP[N+1][3]\) 선언이 필요!

 

\(DP[i][2]\)는 다음과 같이 해석할수 있다

 

\(DP[i][0]\) ==> 처음부터 i번째열의 0행  "까지만" 해결이 되었을 때의 최소의 파견횟수 

\(DP[i][1]\) ==> 처음부터 i번째열의 1행  "까지만" 해결이 되었을 때의 최소의 파견횟수 

\(DP[i][2]\) ==> 처음부터 i번째열의 0행,1행  "둘다" 해결이 되었을 때의 최소의 파견횟수

 

여기서 중요한건 저 DP배열의 점화식이다

 

\(DP[i][0]\) 은 \(DP[i-1][2] + 1\) 이 기본이고

                    \(D[i-1][0] + D[i][0] <= w\) 이 가능한 경우 //앞블록과 현재블록을 묶어 줄수 있는경우

                    \(D[i-1][1]+1\) 둘중 작은값으로 초기화 해준다

 

\(DP[i][1]\) 은 \(DP[i-1][2] + 1\) 이 기본이고

                    \(D[i-1][1] + D[i][1] <= w\) 이 가능한 경우 //앞블록과 현재블록을 묶어 줄수 있는경우

                    \(DP[i-1][0]+1\) 둘중 작은값으로 초기화 해준다

 

\(DP[i][2]\) 은 우선 \(min { DP[i][0]+1 , DP[i][1]+1 }\) 중 최소값으로 초기화 해주고

                    // 위의 두 식을 이용해서 구한식에 더하기 1만해서 경우의수를 일단 초기화할수 있다.

 

                     i-1열까지 완료된 경우의수 + i번째 열 0행 1행 (위 아래) 하나씩 투입을 한경우

                    \(DP[i-1][2]+1\) 과   현재값중 작은값으로

 

                    \(D[i][0] + D[i][1] <= w\) 이 가능한 경우  

                     \(DP[i-1][2]+1\) 와 현재값중 작은값으로

                    //위 아래로 먹는게 가능한 경우

 

                    0행과 1행 모든 두 칸씩 먹는게 가능한 경우

                    \(D[i][0] + D[i-1][0] <= w\)  과  \(D[i-1][1] + D[i][1] <= w\) 이 가능한 경우

                    \(DP[i-2][2]+2\)  와 현재값중 작은값으로

 

이 경우 최종적으로 답이 \(DP[N][2]\) 에 담기게 된다.

 

하지만 이 경우는 1번 열에서부터 정직하게 시작한다는 것을 의미한다

이것만 살펴보게 된다면 1과 N을 묶에 주는경우를 고려 하지 못한다

 

그러면 초반에서 갈라지는 경우의 수를 판단해보면

1.1-N가 바로 만나지 않는 경우

2.\(D[1][0] 과 D[N][0] \)이 만나는 경우

3.\(D[1][1] 과 D[N][1] \)이 만나는 경우

4.\(D[1][0] 과 D[N][0] \) 그리고\(D[1][1] 과 D[N][1] \)이 만나는 경우

 

이 네 가지 경우에 대해서 DP를 돌려주면 된다

각각 경우에 대해서는 가정에서 선택한 방을 고르지 않는 결과를 반영하여야 하는게 주의사항이다

---

코드