16637번: 괄호 추가하기
첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가
www.acmicpc.net
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;
}'알고리즘 문제풀이 > 완탐' 카테고리의 다른 글
| 백준 17135 [C++] (0) | 2020.10.21 |
|---|---|
| 백준 17136 [C++] (0) | 2020.10.20 |
| 백준 17070 [C++] (0) | 2020.10.14 |
| 백준 17281 : 야구 [C++] (0) | 2020.10.13 |
| 백준 1748 : 수 이어 쓰기 1 (0) | 2020.03.24 |
