[BAE/<JOON> 문제풀이] 1006. 습격자 초라기

https://www.acmicpc.net/problem/1006

1006번: 습격자 초라기

 

드디어,, 이 문제를 풀었다,, 

 

PS 공부 처음 시작해서 문제 순서대로 풀 때 딱 이 문제에서 막혔었는데 푸는 날이 오고야 말았다. 

 

핵심::
환형 DP -> 이 유형을 가리키는 정확한 용어가 있는지는 모르겠다. 배열의 앞뒤를 붙이고 푸는 문제 유형이 있는 것 같다.

이 문제를 풀기 전에 프로그래머스에 있는 도둑 문제를 풀어보면 도움이 된다.

풀이::
지금까지 접해본 환형 구조의 DP문제들은 모두 아래와 비슷한 방식으로 해결 할 수 있다. 

주어진 데이터 배열의 처음과 끝을 적당히 이어 붙인 배열 여러개를 검사하여 최적값을 찾는다.

총 4개의 데이터 배열을 연산해 답을 구할 수 있다.

1. 첫번째 / 마지막 적 들을 하나의 특수 소대로 처리하지 않는 경우
2. 안쪽 링에 있는 첫번째 / 마지막 적들을 하나의 특수소대로 처리하는 경우
3. 바깥쪽 링에 있는 첫번째 / 마지막 적들을 하나의 특수소대로 처리하는 경우
4. 안쪽과 바깥쪽 링 모두 첫번째 / 마지막 적들을 하나의 특수 소대로 처리하는 경우

0번은 주어진 배열을 그대로 활용하면 되고
1, 2, 3번은 첫번째 인덱스의 값을 복사해 배열의 마지막에 붙여넣어 만들 수 있다.

점화식::
하나의 특수 소대로 2개 구역을 처리하는 경우를 최대한 늘려야 한다.

DP 배열도 2개 사용한다. 코딩 방식이야 어떻게 해도 상관없지만 그냥 DP 배열을 2개 쓰는게 깔끔했다.

dp1[i][j].v : i번째 구역의 j ( 1 : 상단, 2 : 하단 ) 구역에 있는 적들을 포함하며 세로로 확장했을 때의 하나의 소대로 2개 구역을 처리한 최대 수
dp1[i][j].h : i번째 구역의 j ( 1 : 상단, 2 : 하단 ) 구역에 있는 적을들 포함하며 가로로 확장했을 때의 하나의 소대로 2개 구역을 처리한 최대 수
dp2[i] : i번째 구역까지 하나의 소대로 2개의 구역을 처리한 최대 수

초기값 : 1번 구역은 이전 구역이 없으므로 횡으로 확장은 불가능함.
dp1[1][1].v = (arr[1][1] + arr[1][2] <= k ? 1 : 0)
dp1[1][2].v = (arr[1][1] + arr[1][2] <= k ? 1 : 0)

dp2[1] = (arr[1][1] + arr[1][2] <= k ? 1 : 0)

이후 계산 : 4개의 데이터 테이블에 대해 다음 점화식을 적용하여 계산함.

dp1[i][j].v = dp2[i - 1] + (arr[i][1] + arr[i][2] <= k ? 1 : 0)
: 세로로 확장하는 경우, 이전 구역 최적값 + 이번 구역 세로 처리 가능 여부

dp1[i][1].h = (dp2[i - 2] > dp1[i - 1][2].h ? dp2[i - 2] : dp1[i - 1][2].h) + (arr[i - 1][1] + arr[i][1] <= k ? 1 : 0)
dp1[i][2].h = (dp2[i - 2] > dp1[i - 1][1].h ? dp2[i - 2] : dp1[i - 1][1].h) + (arr[i - 1][2] + arr[i][2] <= k ? 1 : 0)
가로로 확장하는 경우, i - 2구역에서의 최적값과 i - 1 구역 반대쪽에서 가로로 확장한 최적값 중 큰 것을 선택 + 이번 구역 가로 처리 가능 여부

dp2[i] = max(dp1[i][j].v, dp1[i][j].h, dp2[i - 2] + (arr[i - 1][1] + arr[i][1] <= k ? 1 : 0) + (arr[i - 1][2] + arr[i][2] <= k ? 1 : 0))
최종적으로 i번째 구역의 최적값을 결정할때는, 이전에 계산한 구역의 최적값들 이외에 상단 / 하단에서 가로로 2번 확장한 경우를 따로 포함한다. 
이유는 위의 최적값들이 계산한 값들은 상단 또는 하단 한칸의 최적값만 포함하기 때문에 상단/하단 모두 한 소대로 처리하는 경우, 최적값을 제대로 계산하지 못한다.

최종 출력은 n * 2 - max(dp2[dp2.size - 1]) 이다. 전체 구역에서 합쳐진 구역의 갯수를 제외하면 된다.

max인 이유는 총 4개의 배열을 연산하기 때문에 그 중 가장 큰 것을 출력한다는 의미이다.

의견::
환형 구조라서 어려운 줄 알았는데 그냥 점화식이 복잡했다.

체감 난이도는 택배랑 비슷했다.

 

코드 짜고 나서 풀이와 코드가 깔끔하다는 느낌을 받았고 첫 풀이 첫 제출에 AC 맞았다.

 

이건 죽을 때 고인의 개쩌는 모습 목록에 넣어야 된다.

 

( 2022.07.27 가로 / 세로 오류 수정 )

 

코드::

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct dpnode {
	int v, h;
};

int main()
{
	int tc; cin >> tc;
	while (tc--) {
		int n, k; cin >> n >> k;		
		vector<vector<vector<int>>> arr(4, vector<vector<int>>(n + 1, vector<int>(3, 2100000000)));		
	
		for (int i = 1; i <= n; i++) {
			cin >> arr[0][i][1];
		}
		for (int i = 1; i <= n; i++) {
			cin >> arr[0][i][2];
		}

		arr[1] = arr[0];
		arr[2] = arr[0];
		arr[3] = arr[0];

		arr[1].push_back(arr[1][1]);
		arr[2].push_back(arr[2][1]);
		arr[3].push_back(arr[3][1]);

		//복사한 자리들 합치기 불가능으로 설정 ( 추후 DP 탐색 이후 총 결과 - 1 (2n - 1) )
		arr[1][1][1] = k + 1;
		arr[1][n + 1][2] = k + 1;
		arr[2][1][2] = k + 1;
		arr[2][n + 1][1] = k + 1;
		arr[3][1][1] = k + 1;
		arr[3][1][2] = k + 1;

		int mx = -1;

		for (int r = 0; r < 4; r++) {
			int lim = n + (r > 0 ? 1 : 0);
			vector<vector<dpnode>> dp(lim + 1, vector<dpnode>(3));
			vector<int> dpt(lim + 1);
			dp[1][1].v = (arr[r][1][1] + arr[r][1][2] <= k ? 1 : 0);
			dp[1][2].v = (arr[r][1][1] + arr[r][1][2] <= k ? 1 : 0);
			dpt[1] = (arr[r][1][1] + arr[r][1][2] <= k ? 1 : 0);
			for (int i = 2; i <= lim; i++) {
				int s1 = 0, s21 = 0, s22 = 0;
				s1 = dpt[i - 1] + (arr[r][i][1] + arr[r][i][2] <= k ? 1 : 0);
				int p1 = (arr[r][i - 1][1] + arr[r][i][1] <= k) ? 1 : 0;
				int p2 = (arr[r][i - 1][2] + arr[r][i][2] <= k) ? 1 : 0;
				s21 = (dpt[i - 2] > dp[i - 1][2].h ? dpt[i - 2] : dp[i - 1][2].h) + p1;
				dp[i][1].h = s21;
				dp[i][1].v = s1;
				s22 = (dpt[i - 2] > dp[i - 1][1].h ? dpt[i - 2] : dp[i - 1][1].h) + p2;
				dp[i][2].h = s22;
				dp[i][2].v = s1;

				dpt[i] = max({dp[i][1].h, dp[i][1].v, dp[i][2].h, dp[i][2].v, dpt[i - 2] + p1 + p2});
			}
			mx = (mx > dpt[lim] ? mx : dpt[lim]);
		}

		cout << n * 2 - mx << "\n";
	}
	
	return 0;
}