C++ 습격자 초라기 문제 풀기 (백준 1006)

읽어주셔서 감사합니다. 오늘은 백준의 1005번, ACM craft 문제에 대해 풀어보도록 하겠습니다.

*이번 문제도 1005번과 같이 1006번이라는 번호와는 걸맞지 않게 다이나믹 프로그래밍을 사용합니다.

* 혼자 작성 하기는 하였으나, logic1부분은 타 블로그를 조금 참고했습니다. 조금 유감스러운 일입니다.

참고한 블로그 주소

---

code

#include <stdio.h>
#include <string.h>
#include <limits.h>

#define INF	20001

#define MIN(x, y)	(((x) < (y))? (x) : (y))
#define MAX(x, y)	(((x) > (y))? (x) : (y))

int N, T, W;
int dy[10002][3];
int val[10002][2];

enum{fir, sec, whl};

void logic1(const int st) {
	for (int i = st; i <= N; i++) {
		int fir_fill = (val[i][fir] + val[i - 1][fir] <= W) ? 1 : 2;
		int sec_fill = (val[i][sec] + val[i - 1][sec] <= W) ? 1 : 2;
		int whl_fill = (val[i][fir] + val[i][sec] <= W) ? 1 : 2;

		dy[i][fir] = MIN(dy[i - 1][whl] + 1, dy[i - 1][sec] + fir_fill);
		dy[i][sec] = MIN(dy[i - 1][whl] + 1, dy[i - 1][fir] + sec_fill);

		dy[i][whl] = MIN(dy[i][fir] + 1, dy[i][sec] + 1);
		dy[i][whl] = MIN(dy[i][whl], dy[i - 1][whl] + whl_fill);
		dy[i][whl] = MIN(dy[i][whl], dy[i - 2][whl] + fir_fill + sec_fill);
	}
	return;
}

int main(void) {
	int valt;
	scanf("%d", &T);
	for (int hg = 0; hg < T; hg++) {
		memset(val, 0, sizeof(val));
		memset(dy, 0, sizeof(dy));

		scanf("%d %d", &N, &W);
		for (int i = 1; i <= N; i++) { scanf("%d", &val[i][fir]); }
		for (int i = 1; i <= N; i++) { scanf("%d", &val[i][sec]); }

		if (N == 1) {
			printf("%d\n", (val[1][fir] + val[1][sec] <= W) ? 1 : 2);
			continue;
		}

		dy[1][fir] = dy[1][sec] = 1;
		dy[1][whl] = ((val[1][fir] + val[1][sec]) <= W) ? 1 : 2;
		logic1(2);
		valt = dy[N][whl];

		dy[0][whl] = INF;
		if (val[1][fir] + val[N][fir] <= W) {

			dy[1][fir] = 1;
			dy[1][sec] = INF;
			dy[1][whl] = 2;
			logic1(2);

			valt = MIN(valt, dy[N][sec]);
		}

		if (val[1][sec] + val[N][sec] <= W) { //not else if
			dy[1][fir] = INF;
			dy[1][sec] = 1;
			dy[1][whl] = 2;
			logic1(2);

			valt = MIN(valt, dy[N][fir]);
		}

		if ((val[1][fir] + val[N][fir] <= W) && (val[1][sec] + val[N][sec] <= W)) { //unoptimizationed
			dy[1][fir] = dy[1][sec] = INF;
			dy[1][whl] = 2;
			logic1(2);

			valt = MIN(valt, dy[N - 1][whl]);
		}

		printf("%d\n", valt);
	}
	return 0;
}

---

code

이번 문제는 조건이 조금 복잡한 다이나믹 프로그래밍입니다.
dy[n][i]의 정의는 아래와 같습니다.

 

우선 enum을 통해 fir은 0으로, sec는 1로, whl(whole)은 2로 정의해주었습니다.
enum을 모르시면 약간의 혼란이 있을 수 있으나, 이해하면 가독성이 상당히 높아지죠.

enum설명 사이트

dy[n][fir]	n번째 열의 내부 한 곳만 채우는 경우
dy[n][sec]	n번쨰 열의 외부 한 곳만 채우는 경우
dy[n][whl]	n번쨰 열을 모두 채우는 경우

그리고 dy[i][0]의 계산식은 아래와 같죠

* val[n][fir]는 원타곤의 n열 내부 구역에 있는 적의 수, val[n][sec]는 원타곤의 n열 외부 구역에 있는 적의 수 입니다.

fir_fill	dy[n][fir] + dy[n-1][fir] <= W 가 성립하면 1 아니면 2
sec_fill	dy[n][sec] + dy[n-1][sec] <= W 가 성립하면 1 아니면 2
whl_fill	dy[n][fir] + dy[n][sec] <= W 가 성립하면 1 아니면 2

 

dy[n][fir]	dy[n-1][whl] + 1 dy[n-1][sec] + fir_fill 중 작은 수
dy[n][sec]	dy[n-1][whl] + 1 dy[n-1][fir] + sec_fill 중 작은 수
dy[n][whl]	dy[n][fir] + 1 dy[n][sec] + 1 dy[n-1][whl] + whl_fill dy[n-2][whl] + fir_fill + sec_fill 중 작은 수

그리고 다이나믹의 초기값은 원타곤이 원형이기에, 4종류가 있습니다.

1) 첫 번쨰와 마지막 열이 한 소대로 정리되는 경우가 없을때

2) 첫 번쨰와 마지막 열이 내부에서만 한 소대로 정리 될 때 (val[1][fir] + val[N][fir] <= W이면 초기값이 형성 가능)

3) 첫 번째와 마지막 열이 외부에서만 한 소대로 정리 될 때 (val[1][sec] + val[N][sec] <= W이면 초기값이 형성 가능)

4) 첫 번째와 마지막 열이 내부, 외부에서 모두 한 소대로 정리될때 (2, 3의 조건이 모두 성립하면 초기값이 형성 가능)

 

이 초기값과 점화식을 통해서 올바른 값을 계산할 수 있습니다.
당연히 결괏값은 각 초기값에서 계산된 값들의 최소입니다.

---

use

백준 1006번 참고

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

1006번: 습격자 초라기

---

실행화면

프로그램의 사용 목적을 고려하여 실행화면은 생략하도록 하겠습니다.