[백준/BOJ] 2499번 의좋은 형제

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

2499번: 의좋은 형제

처음 봤을 때 N의 수가 적어서 상대적으로 쉬울 줄 알고 도전했던 문제였다. 하지만 안 쉬웠다.....

매우 많이 틀렸고 다시 생각한 풀이로도 답이 틀리길래 답을 찾아봤더니 마지막 형의 땅 개수 찾는 부분에서 N까지 보지 않고 N-1까지만 봐서 틀렸다... 사소한 착각이 정말 시간을 많이 잡아먹었어서 힘들었던 문제. 정확하게 생각하고 기억하는 것이 중요하다는 걸 다시 느꼈다ㅜㅜ. 필기를 꼼꼼히 해보자ㅜㅜ

 

 

 

 

처음 생각한 방법은 2차 디피였다. 

구조가 gap[25][25]배열이 있고 dp[25][25]가 있는데,
1. gap[i][j]= j열에서 동생(위)이 i칸을 차지했을 때 형(아래)과 차이량(양수,음수 존재) == 위 - 아래
이고
2. dp[j][i]= 현재 위치(j,i)에서의 차이량(==gap[j][i])+dp[k][i-1](k:N~j )까지 보면서
차이량이랑 디피 값의 합의 절댓값이 앞서 저장해놨던 절댓값보다 작아질 때 dp 업데이트하고 절댓값 저장하는 변수 업데이트하기

이런 식을 dp 채워서 abs(dp[i][N-1])(i:0~N) 값 중 가장 작은 게 차이량 제일 적은 경우라고 생각했다.

하지만 이런 식으로 하면 현재 조금 손해 보더라도 나중에 더 작아질 수 있는 가능성을 보지 못한다는 것을 알게 되었고, 알고리즘을 엎었다ㅜㅜ.

 

<처음 코드> 

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<stack>
using namespace std;
int adj[25][25];
int d[25];
int re[25];
int N;
int gap=1000000000;



int main(void) {
	scanf("%d", &N);
	int sum[25][25] = { 0 };
	int gap[25][25] = { 0 };
	int t = 0, b = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf(" %d", &adj[i][j]);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if(j==0)sum[j][i]= adj[j][i];
			else sum[j][i] = sum[j-1][i] + adj[j][i];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= N; j++) {
			if (j == 0)gap[j][i] = -sum[N-1][i];
			else gap[j][i] =sum[j-1][i] - (sum[N-1][i] - sum[j-1][i]); //위-아래
		}
	}
	int dp[25][25] = { 0 };
	int parent[25][25] = { 0 };
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= N; j++) {
			if (i == 0)dp[j][i] = gap[j][i];
			else {
				int m = 1000;
				for (int k = N; k >= j; k--) {
					if (m > abs(gap[j][i]+dp[k][i-1])) {
						dp[j][i] = gap[j][i] + dp[k][i-1];
						m = abs(gap[j][i] + dp[k][i-1]);
						parent[j][i] = k;
					}
				}
			}
		}
	}
	stack<int>st;
	int result=10000;
	int start;
	for (int i = 0; i <= N; i++) {
		if (result> abs(dp[i][N - 1])) {
			start = i;
			result = abs(dp[i][N - 1]);
		}
	}
	st.push(start);
	for (int i = N - 1; i >0; i--) {
		st.push(parent[start][i]);
		start = parent[start][i];
	}
	printf("%d\n",result);
	while (!st.empty()) {
		printf("%d ", N - st.top());
		st.pop();
	}
	printf("\n");
	return 0;
}

<반례>

3
2 2 10
2 2 1
2 6 1

---

<해결 방법>

 

그래서 지금 손해 보더라도 나중에 이득인 경우를 봐주기 위해 3차원으로 늘려서 dp [x][y][bro]를 만들었다.

1. bro(3차): (x, y) 위치에서까지 오기까지 거쳐온 동생이 갖는 수확량.

2. dp 값은 형 동생의 차이량.

 

재귀 함수로 쭉 바닥까지 들어가서 마지막 열에 도착하면 해당 위치까지의 동생의 수확량이 3번째 인덱스에 저장되어있어 형과의 차이량을 구하여 저장하고 이 값을 리턴한다. 이렇게 리턴된 값들을 비교하여 가장 작은 값을 또 저장하고 리턴한다.

 

이런 식으로 동생이 x값의 수확량을 가질 때, 형과 가장 차이가 작게 나는 값이 각각의 dp 값이 저장이 되고,

마지막 리턴 값에는 처음 지정한 첫열에서의 동생 땅의 개수에서 구할 수 있는 최소 차이량을 알 수 있게 된다.

이 방식을 동생이 첫 열에 땅을 0개부터 N개까지 선택하는 것을 생각해 N+1번을 돌면 전체 경우 중 최소 차이량을 구할 수 있다.

 

형이 갖게 되는 땅의 모양은 찾은 최소 차이량과 같은 값을 가지는 dp위치를 찾아서 들어가면서 같으면 해당 열을 저장한다.

 

 

 

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<stack>
using namespace std;
int adj[25][25];
int N;
int allsum = 0;
int sum[25][25] = { 0 };
int gap[25][25] = { 0 };
#define INF 987654321 
int dp[25][25][50000];
int store[25];
int func(int x, int y, int young) {
	if (dp[x][y][young] >= 0) {
		return dp[x][y][young];
	}
	if (y == N-1) {
		dp[x][y][young] = abs(young-(allsum-young));
		return dp[x][y][young];
	}
	int re=5000000;
	for (int i = x; i >= 0; i--) {
		int pre = func(i, y + 1, young + sum[i][y + 1]);
		if (re > pre) {
			re = pre;
		}
	}
	dp[x][y][young] = re;
	return dp[x][y][young];
}
void func2(int x, int y, int young,int find) {
	if (dp[x][y][young] == find) {
		store[y] = x;
		for(int i=x;i>=0;i--)func2(i, y + 1, young + sum[i][y + 1],find);
	}
	return;
}


int main(void) {
	scanf("%d", &N);
	int t = 0, b = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf(" %d", &adj[i][j]);
			allsum += adj[i][j];
		}
	}
	for (int i = 0; i < N; i++) { // 한 열씩 더하기
		for (int j = 1; j <= N; j++) {
			if (j == 0)continue;
			if(j==1)sum[j][i]= adj[j-1][i];
			else sum[j][i] = sum[j-1][i] + adj[j-1][i];
		}
	}
	int re = 500000;
	memset(dp, -1, sizeof(dp));
	int resultnum[25] = { 0 };
	for (int i = 0; i <= N; i++) {
		int pre = func(i, 0, sum[i][0]);
		if (re > pre) {
			//store[0] = i;
			re = pre;
		}
	}
	for (int i = 0; i <= N; i++) {
		if (dp[i][0][sum[i][0]] == re) {
			store[0] = i;
			func2(i, 0, sum[i][0], re);
			break;
		}
	}
	printf("%d\n", re);
	for (int i = 0; i < N; i++)printf("%d ",N-store[i]);
	printf("\n");
	return 0;
}