프로그래머스: 사칙연산⭐⭐⭐⭐
카테고리: Programmers
태그: Algorithm, Blog, C++, Programmers
체감 난이도 : ⭐⭐⭐⭐
유형 : DP
걸린 시간: 1시간 초과!
🧐 문제
문제 설명
사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다.
- ((1 - 5) - 3) = -7
- (1 - (5 - 3)) = -1
위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다.
또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다.
- (((1 - 3) + 5) - 8) = -5
- ((1 - (3 + 5)) - 8) = -15
- (1 - ((3 + 5) - 8)) = 1
- (1 - (3 + (5 - 8))) = 1
- ((1 - 3) + (5 - 8)) = -5
위와 같이 서로 다른 연산 순서의 계산 결과는 [-15, -5, -5, 1, 1]이 되며, 이중 최댓값은 1입니다.
문자열 형태의 숫자와, 더하기 기호(“+”), 뺄셈 기호(“-“)가 들어있는 배열 arr가 매개변수로 주어질 때, 서로 다른 연산순서의 계산 결과 중 최댓값을 return 하도록 solution 함수를 완성해 주세요.
제한 사항
- arr는 두 연산자 “+”, “-“ 와 숫자가 들어있는 배열이며, 길이는 3 이상 201 이하 입니다.
- arr의 길이는 항상 홀수입니다.
- arr에 들어있는 숫자의 개수는 2개 이상 101개 이하이며, 연산자의 개수는 (숫자의 개수) -1 입니다.
- 숫자는 1 이상 1,000 이하의 자연수가 문자열 형태로 들어있습니다.. (ex : “456”)
- 배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있습니다.
입출력 예
| arr | result |
|---|---|
| [“1”, “-“, “3”, “+”, “5”, “-“, “8”] | 1 |
| [“5”, “-“, “3”, “+”, “1”, “+”, “2”, “-“, “4”] | 3 |
입출력 예시
입출력 예 #1
위의 예시와 같이 (1-(3+(5-8))) = 1 입니다.
입출력 예 #2
(5-(3+((1+2)-4))) = 3 입니다.
✏️ 풀이 과정
DP를 사용하여 푸는 문제였다.
핵심
- 1 - 3 + 5 - 8로 이루어져 있다면,
좌측, 연산자, 우측으로 재귀적으로 분리해나가면 된다. - 연산자가
-인가+인가에 따라 최대 값으로 만드는 방법이 달라진다. - 최대 값으로 만드는 경우는 다음과 같다:
-인 경우: 좌측은최대 값, 우측은최소 값이어야 한다.+인 경우: 좌측은최대 값, 우측은최대 값이어야 한다.
- 최소 값으로 만드는 경우는 다음과 같다:
-인 경우: 좌측은최소 값, 우측은최대 값이어야 한다.+인 경우: 좌측은최소 값, 우측은최소 값이어야 한다.
- 즉, DP에 최소 값과 최대 값을 함께 저장해두어야 한다.
🔸 1 - 3 + 5 - 8 을 나누는 예시
| left | operator | right |
|---|---|---|
| 1 | - | 3+5-8 |
| 1-3 | + | 5-8 |
| 1-3+5 | - | 8 |
🔸 3 + 5 - 8 을 나누는 예시
| left | operator | right |
|---|---|---|
| 3 | + | 5-8 |
| 3+5 | - | 8 |
✏️ 나의 풀이
#include <bits/stdc++.h>
#include <climits>
using namespace std;
bool visited[201][201] = {false, };
int dp[201][201][2] = {0, };
pair<int, int> dfs(vector<string>& arr, int l, int r) {
if(visited[l][r]) return { dp[l][r][0], dp[l][r][1] };
if(l==r) {
return { stoi(arr[l]), stoi(arr[l]) };
}
int max_val = INT_MIN;
int min_val = INT_MAX;
for(int k=l; k<=r-2; k+=2) {
pair<int, int> l_val = dfs(arr, l, k);
pair<int, int> r_val = dfs(arr, k+2, r);
int min_temp;
int max_temp;
if(arr[k+1] == "-") {
min_temp = l_val.first - r_val.second;
max_temp = l_val.second - r_val.first;
} else {
min_temp = l_val.first + r_val.first;
max_temp = l_val.second + r_val.second;
}
max_val = max(max_temp, max_val);
min_val = min(min_temp, min_val);
}
visited[l][r] = true;
dp[l][r][0] = min_val;
dp[l][r][1] = max_val;
return { min_val, max_val };
}
int solution(vector<string> arr)
{
return dfs(arr, 0, arr.size()-1).second;
}
✔️ 다른 사람의 풀이
function solution (arr) {
const operandsCount = Math.ceil(arr.length / 2);
const max_dp = new Array(operandsCount).fill().map(_ => new Array(operandsCount).fill(-Infinity));
const min_dp = new Array(operandsCount).fill().map(_ => new Array(operandsCount).fill(Infinity));
# dp 초기값 저장
for(let i = 0; i < operandsCount; i++) {
max_dp[i][i] = +arr[i*2];
min_dp[i][i] = +arr[i*2];
}
for(let cnt = 1; cnt < operandsCount; cnt++) {
for(let i = 0; i < operandsCount - cnt; i++) {
const j = i + cnt;
for(let k = i; k < j; k++) {
if (arr[k*2+1] === '+') {
max_dp[i][j] = Math.max(max_dp[i][j], max_dp[i][k] + max_dp[k+1][j]);
min_dp[i][j] = Math.min(min_dp[i][j], min_dp[i][k] + min_dp[k+1][j]);
} else {
max_dp[i][j] = Math.max(max_dp[i][j], max_dp[i][k] - min_dp[k+1][j]);
min_dp[i][j] = Math.min(min_dp[i][j], min_dp[i][k] - max_dp[k+1][j]);
}
}
}
}
return max_dp[0][operandsCount-1];
}
🧐 분석
- 재귀가 아닌, 3중 포문으로 구현하고 있다.
나의 코드보다 성능능이 좋다. - 이 외 전체적인 흐름은 같다.
🪶 후기
처음에 봤을 때, 범위가 아닌 숫자로 DP를 구현해야하나 싶었다.
범위가 아닌 숫자로 DP를 구현하면,
1-2+3+1-2+3+...+1-2+3과 같은 반복되는 입력도 빠르게 처리할 수 있기 때문이다.
하지만 이를 처리하기엔 쉽지 않아 보였고, 해답도 쉽게 떠오르지 않았다.
언젠가 시간이 된다면, 이에 대해 더 생각해보는 것도 재밌을 것 같다.
댓글남기기