글 읽기 - 염치불구하고 틀린 이유 질문드립니다.

cydphj 3년 전 1

입력 예제와 게시판에 있는 반례들에 대해 오류가 나타나지 않고, 스스로 반례를 계속 생각해봤지만 떠오르지 않아 염치불구하고 질문드립니다.

저는 pair<int, int> 자료형을 사용해서 first에는 '연속합' 문제에서와 같이 동일하게 메모이제이션했고, second에는 i번째 입력 원소가 음수일 경우 해당 원소를 제거했을 경우의 연속합 계산값을 메모했습니다.

어느 곳에서 논리적으로 오류를 범했는지 조언해주시면 정말 감사하겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<int> vec;
vector<pair<int, int>> dp;
// first에는 기존 연속합 저장, second에는 해당 원소를 제거했을 경우의 연속합 저장.

int solve() {
	if (N == 1) return vec[0];    // 원소가 하나인 경우 아래 과정은 불필요함.

	dp[0].first = vec[0], dp[0].second = 0;
	for (int i = 1; i < N; ++i) {
        // [분기 1] - 현재 값이 (이전 연속합 + 현재값)보다 작다면 연속합에 포함한다.
		if (vec[i] < dp[i - 1].first + vec[i]) {
			dp[i].first = dp[i - 1].first + vec[i];
			dp[i].second = (vec[i] < 0) ? dp[i - 1].first : dp[i - 1].second + vec[i];
		} else {    // [분기 2] - 연속을 끊고 현재 값을 유지하는게 이득인 경우,
			dp[i].first = vec[i];
			dp[i].second = (vec[i] < 0) ? dp[i - 1].first : dp[i - 1].second + vec[i];
		}
	}
    // 최대값을 구하는 과정
	int temp1 = dp[0].first, temp2 = dp[1].second;
	for (int i = 1; i < N; ++i) {
		if (temp1 < dp[i].first) temp1 = dp[i].first;
		if (temp2 < dp[i].second) temp2 = dp[i].second;
	}
	return max(temp1, temp2);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N;
	vec = vector<int> (N);
	for (int i = 0; i < N; ++i) cin >> vec[i];
	dp = vector<pair<int, int>> (N);
	
	cout << solve() << '\n';
}

Coxie 3년 전 1

dp[i].second = (vec[i] < 0) ? dp[i - 1].first : dp[i - 1].second + vec[i];

이게 문제인것 같군요.

vec[i]가 음수라고 해서 무조건 손해가 아닌것 같습니다.

예컨데, 중간에 -999같은게 있고, vec[i]가 -1인 상황에서, dp[i-1].first를 선택하는 것(-999를 택하는 행위)보다 dp[i-1].second+vec[i]를 택하는 것이 현명합니다

cydphj 3년 전 1

조언 주셔서 정말 감사합니다. 주신 조언 토대로 조금 더 깊게 고민해보니 제 논리가 틀렸음을 알 수 있었습니다.

말씀하신대로 'vec[i]가 음수라고 선택하지 않는 것이 최적해로 향하는 방법이 아님'을 발견했습니다.

찾은 반례는 다음과 같습니다.

-1 700 -500 -150 1000 -100

인 경우 최적해는 1550이지만, 제 풀이로는 1200이 나오게 됩니다.

틀린 가정으로 문제를 풀게되니 올바른 답이 나오지 않았습니다. 결국 이 문제를 제대로 풀기 위해서는 i번째 이전까지의 최대 연속합과 i번째 이후의 최대 연속합이 나오는 조합을 모두 구해보고 최적해를 구해야 한다는 점을 깨달았습니다. 감사합니다.

Coxie 3년 전 1

그냥 dp[i].second = (vec[i] < 0) ? dp[i - 1].first : dp[i - 1].second + vec[i];

이걸

dp[i].second = max(dp[i - 1].first, dp[i - 1].second + vec[i]);

이걸로 바꿔도 되지 않나요?

cydphj 3년 전 0

네 맞습니다 first와 second + vec[i] 값을 비교해서 더 큰 값을 계속 가지고 가면 됩니다 ㅎㅎㅎ 도와주셔서 정말 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

염치불구하고 틀린 이유 질문드립니다.

cydphj 3년 전 1

Coxie 3년 전 1

cydphj 3년 전 1

Coxie 3년 전 1

cydphj 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말