글 읽기 - 어디가 잘못됐을까요? dp로 풀었습니다

subin7557 4년 전 0

dp로 풀었습니다...

아예 틀렸다고 뜨는데

어떤 로직이 잘못된걸까요...

예제나 질문에있는 반례는 잘 나옵니다 ㅠㅠ

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int cal(int a, int b, char c) {
	if (c == '+')
		return a + b;
	else if (c == '-')
		return a - b;
	else
		return a * b;

}
void solve(int N, string s) {
	int num[20] = { 0 };
	for (int i = 0; i < N; i += 2) {
		num[i] = s[i] - '0'; //숫자는 int로 저장 => i가 짝수일때만 숫자
	}
    
	int dp[20][2] = { 0 };
    //dp[i][0] : 괄호없을때, dp[i][1] : 괄호있을때
    // i는 짝수만 사용 => 식이랑 인덱스 맞추기위해
    
    //첫번째 숫자
	dp[0][0] = num[0]; 
	dp[0][1] = num[0];
	
    //식 크기가 1이상일때
    if (N > 1) {
        // 1번숫자랑 2번숫자 계산한값
		dp[2][0] = cal(num[0], num[2], s[1]);
		dp[2][1] = dp[2][0];
	}
    
	for (int i = 4; i < N; i += 2) {
		//괄호 x
		dp[i][0] = max(cal(dp[i - 2][0], num[i], s[i - 1]), cal(dp[i - 2][1], num[i], s[i - 1]));
        
		//괄호 o
		int tmp = cal(num[i - 2], num[i], s[i - 1]);
		dp[i][1] = max(cal(dp[i - 4][0], tmp, s[i - 3]), cal(dp[i - 4][1], tmp, s[i - 3]));
	}
	cout << max(dp[N - 1][0], dp[N - 1][1]);
}
int main() {
	int N;
	string s;
	cin >> N >> s;
	solve(N, s);
}

choko100 4년 전 1

위의 dp 코드의 경우 바로 앞에서 계산된 값들 중에서 최댓값으로 이어질 수 있는 것을 선택하기 때문에 문제가 되는 것 같습니다. 계속 음수가 나오다가 마지막에 양수가 되서 숫자가 커질 수 있는 경우를 고려하기 어려울 것 같습니다.

3-2*8-9*9+9*8-9*9+9

를 입력해보시면 7128이 나와야 하는데 972가 나옵니다.

7128의 경우 (3-2*8-9)*(9+9)*(-1)*(18) 와 같은 순서로 계산되고,

972의 경우 ((3-2)*(8-9)*9+9*8-9)*(9+9)와 같은 순서로 계산됩니다.

subin7557 4년 전 0

앗 감사합니다!!

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

문제

문제

출처

ICPC

어디가 잘못됐을까요? dp로 풀었습니다

subin7557 4년 전 0

choko100 4년 전 1

subin7557 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말