BOJ #2229. 조 짜기 (Gold 하위권)

dp문제를 풀다가 어서 아이디어 까먹기 전에 기록해야겠다고 생각해 허겁지겁 포스팅하게 되었습니다.

(원래 오늘 안쓰려 했는데 ㅠㅠ)

www.acmicpc.net/problem/2229

2229번: 조 짜기

백준 2229번. 조 짜기 문제입니다.

이 문제는 친구가 추천해준 문제인데, 개인적으로 저한테는 생각보다 얻어갈 점이 많아서 좋았던 문제입니다.

---

의식의 흐름.

처음엔 문제를 잘못 읽어서 pair<int, int>로 나이, 점수를 저장시켜야 된다고 생각해 꽤나 어려운 dp라 생각했습니다.

그런데, 생각해보니 나이는 순서대로 주어지니까 결국, N개의 수가 주어질 때, 적절히 분할해서

최대의 점수를 뽑아내는 분할의 경우를 구해주면 된다고 생각했습니다.

이 때까지 저는 그냥 무난히 풀리는 쉬운 dp라 생각했었죠...

그런데, 풀면 풀수록 자꾸 예제 답이 29가 나오는 겁니다. 굉장히 애먹었습니다..

(+ 저는 dp는 웬만해선 탑다운(top-down)으로 풉니다. 탑다운이 무난하니 쉽더라구요...)

---

해결 방법.

// 자기 자신에 대한 정보를 담고,
// 다음 턴으로 넘어가야 된다.
// 따라서 cur+1부터 적용하면 안된다.
for (int i = cur; i < N; i++) {
	m = min(m, a[i]);
	M = max(M, a[i]);
	ret = max(ret, dp(i + 1) + M - m);	// M-m을 더해줘야 한다.
}

이 부분이 중요합니다.

처음에 저는 i=cur+1부터 돌아서 도대체 자기 자신의 정보를 도대체 어떻게 담을까?

아주 별 짓을 다했습니다.

 

함수 인자로 minNum, maxNum을 따로 지정해서 최소, 최대를 담고 다음 턴으로 넘어갈까?

근데 이렇게 하면, 다른 팀원끼리의 차의 합을 구해버려서 예제 답이 29가 나오더라구요.

그리고, cur+1부터 돌기 시작하면, [최대/최소]가 자신의 정보가 아닌, 그 다음 항의 [최대/최소]정보가 담겨진 상태로 넘어가기 때문에 그런것도 있고요.

---

 

그럼 for문으로 다음항(cur+1) 탐색하는 블록 '밖'에 빼놓고 최대/최소를 구하면 되지 않느냐?

---

*주의! 틀린 코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 1001;
int N, a[MAX], d[MAX], ans;
int dp(int cur, int m, int M) {
	int& ret = d[cur];	// dp table
	if (ret != -1)
		return ret;
	if (cur == N)
		return ret = 0;
	ret = 0;
	// 달라진 부분
	int n1= min(m, a[cur]);
	int n2= max(M, a[cur]);
	// cur+1부터 돌아보는 코드
	for (int i = cur+1; i < N; i++) {
		ret = max(ret, dp(i, n1, n2) + n2 - n1);	// M-m을 더해줘야 한다.
	}
	return ret;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	fill(d, d + MAX, -1);
	// 처음엔 최소, 최대가 a[0]
	cout << dp(0, a[0], a[0]) << "\n";
}

하하하 이렇게 말씀이신가요?

(틀린 이유를 바로 알아야 합니다! 모르셔도 괜찮습니다. 밑에 이유가 나와요 ㅎㅎ)

 

우선, 최대 최소를 구하는 코드를 (n1, n2를) 보시다 시피 for문 바깥으로 빼냈습니다.

만약 이렇게 할 경우, 최대, 최소는 비교할 것이 없어지므로 무조건 a[cur]로만 지정되는데, 이러면 최대 최소가 아닌 a[cur]이나 마찬가지이기 때문에, 최대 최소를 지정해주기 위해 인자로 그 전 자신의 최대, 최소를 넘겨주었습니다.

 

물론 이렇게도 해봤습니다. 이렇게 하면 예제 답이 48이 나올겁니다!! (...ㅠㅠ)

 

일단, 예제가 N=10으로 너무 기니까,

4
8 6 9 3
ans: 8

적당한 길이인 이 예제로 비교해보죠. 참고로 위 코드대로 하면, 이 예제 답은 5가 나옵니다.

1. 처음엔 a[0]이 전달되므로 n1=8, n2=8로 dp(1, 8, 8)+0을 재귀호출 하겠네요.
2. 그다음엔 n1=6, n2=8로 dp(2,6,8)+2를 재귀호출 하겠네요.
3. dp(3,6,9)+1을 호출합니다.
4. 하하하... cur+1부터 탐색하니까 dp(4,3,9)+6을 호출하지도 못하네요

사실 더 심각한 이유도 있습니다. 이 코드 또한, 다른 팀원인데도 점수차를 구한다는 점이죠.

저 위의 틀린 코드를 보셨을 때, 이 점을 파악하셨다면 이 문제를 잘 해결하셨을 겁니다. (그럼 이 포스팅을 안보실려나..?)

그 이유는 사실 이 코드는 최대, 최소가 어디에 있으면 해결되는 그런 문제가 아닙니다.

애초에 인자로 최대, 최소를 준 것 자체가 잘못된 것이었습니다.

최대, 최소를 인자로 준 이상 분명 이제 다른 팀으로 넘어가서 탐색하는데, 그 전항의 다른 팀의 팀원차까지 고려 해버리게 되겠죠.

 

 

따라서 이 문제는 자기 자신부터 탐색해서, 자기 자신까지 포함되는 팀원의 최대/최소 정보를 담아서

다음 팀으로 넘어갈 때는, 아예 최대/최소 정보를 넘겨주지 않는 것이 중요합니다.

 

 

ㅎㅎ... 아직 다르게 푸는 방법은 잘 모르겠네요.

참고로 바텀업 난이도도 탑다운이랑 비슷한 것으로 알고 있습니다.

---

주의사항 및 반례.

 

위에 설명한 내용에 주의사항 및 반례가 있습니다.

---

소스 코드.

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 1001;
int N, a[MAX], d[MAX], ans;
int dp(int cur) {
	int& ret = d[cur];	// dp table
	if (ret != -1)
		return ret;
	if (cur == N)
		return ret = 0;
	ret = 0;
	int m = a[cur], M = a[cur];
	// 자기 자신에 대한 정보를 담고,
	// 다음 턴으로 넘어가야 된다.
	// 따라서 cur+1부터 적용하면 안된다.
	for (int i = cur; i < N; i++) {
		m = min(m, a[i]);
		M = max(M, a[i]);
		ret = max(ret, dp(i + 1) + M - m);	// M-m을 더해줘야 한다.
	}
	return ret;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	fill(d, d + MAX, -1);
	cout << dp(0) << "\n";
}

조언 및 피드백 언제나 환영입니다!