백준 16637 [C++]

www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

1.풀이방법

 

- 수식과 정수를 나누는 작업을 따로 하지는 않았고 모두 index를 통해서 접근하였습니다.

 

- 모든 경우의 수를 재귀를 통해서 구현한 후 연산하시면 됩니다.

 

- 처음에 문제조건을 파악하고 무조건 dp라고 생각하고 반복문을 이용해서 바텀업 방식으로 구현을 했는데

 

- 계속 틀렸다고 나와서 방식을 약간 바꿨는데......하 아직도 첫 소스에서는 어떤 사항을 잡지 못하는지

 

- 모르겠네요...... 역시 테스트케이스는 되는데 제출하면 틀릴 때는 참 예외사항 발견하기가 어렵네요

 

- 두번째로 틀린 소스도 올릴테니 지적과 조언좀 부탁드려요...(뭐가 잘못 되었을 까요......ㅠ)

 

 

 

 

 

2. 주의사항

 

- 어이가 없지만.......1일 경우 if문을 걸어 그냥 바로 출력하게끔 했는데,,,,, return 0;을 안줘서

 

- 계쏙 88퍼 쯤에서 틀렸습니다....ㅎ...한참 고민했는데 어이가 없었네요.....기본적인 실수를 줄이도록...해야겠습니다...

 

 

 

 

 

3. 나의 코드

 

<정답 코드>

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


int N;
string inputs;
vector<long long> maxresult;
long long tmpnum;

long long cal(long long num1, long long num2, char c) {
	if (c == '+') { return num1 + num2; }
	else if (c == '-') { return num1 - num2; }
	else {
		return num1 * num2;
	}
}
void dfs(int index, long long nowvalue) {
	if (index >= N - 1) {
		maxresult.push_back(nowvalue);
		return;
	}
	tmpnum = cal(nowvalue, inputs[index + 2] - '0', inputs[index + 1]);
	dfs(index + 2, tmpnum);
	if (index + 4 <= N - 1) {
		long long first = cal(inputs[index + 2] - '0', inputs[index + 4] - '0', inputs[index + 3]);
		tmpnum = cal(nowvalue, first, inputs[index + 1]);
		dfs(index + 4, tmpnum);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	cin >> inputs;
	if (N == 1) { cout << inputs[0] - '0' << "\n"; return 0; }
	dfs(0, inputs[0] - '0');
	sort(maxresult.begin(), maxresult.end());
	cout << maxresult[maxresult.size() - 1] << "\n";
	return 0;
}

 

 

<오답 코드>  ---- 지적해주세요 !ㅠㅠ

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

long long dp[20]; // 결과를 저장할 테이블
int N;
string inputs;

long long cal(long long num1, long long num2, char c) {
	if (c == '+') { return num1 + num2; }
	else if (c == '-') { return num1 - num2; }
	else {
		return num1 * num2;
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	cin >> inputs;
	dp[0] = inputs[0] - 48;
	dp[2] = cal(inputs[0] - 48, inputs[2] - 48, inputs[1]);
	if (N == 1) { cout << dp[0] << "\n"; return 0; }
	if (N == 3) {cout << dp[3] << "\n"; return 0;}
	for (int i = 4; i < N; i += 2) {
		long long first = cal(inputs[i - 2] - 48, inputs[i] - 48, inputs[i - 1]);
		first = cal(dp[i - 4], first, inputs[i - 3]);
		long long second = cal(dp[i - 2], inputs[i] - 48, inputs[i - 1]);
		dp[i] = max(first, second);
	}
	cout << dp[N - 1] << "\n";
	return 0;
}