[알고리즘][X][RE] 사칙연산
2023. 7. 16. 15:12ㆍ알고리즘 풀이
문제 설명
사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 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 입니다.
나의 풀이
- 어떻게 풀어야할지 감이 안와 해설을 보았으나 아직 이해가 안되는 상태
- 다시 이해해보겠다.
def solution(arr):
# 최댓값 문제가 나왔으므로 세 가지 경로가 있음
# 그리디, 탐색, DP
# 어떻게 선택하는게 최선일지 모르기 때문에 그리디는 패스
# 괄호를 넣는 것도 경로가 가야할 방향이 불확실하기 때문에 패스
# 그럼 DP
# 길이가 201개 밖에 안된다 상당히 짧다. for문을 여러번 써도 괜찮다
# 숫자에 집중해야 할 거 같다. 숫자가 묶이는 순서에 집중하자.
# 예제를 보면 드는 생각은 우선 더하기를 진행하고 뺄셈은 나중에 진행하는게 좋다는 생각이다.
# 관건은 -와 - 사이에 있는 +들을 어떤 순서로 처리할 지인 듯하다.
# 일단 + 는
# DP는 완전탐색에 이용
참고해서 푼 풀이
- dp를 두 개를 쓴게 핵심
- if step == 0: 부분에서 max_dp는 설정했는데 min_dp는 설정을 안했음. 이거 찾는데 되게 오래 걸림
- 알고리즘이 적용되는 순서는 다음과 같다.
예를 들어, 10 - 5 + 7 - 5가 주어지면
step 0은 생략하고 step 1부터 10 - 5, 5 + 7, 7 - 5가 계산된다.
step2는 10 - 5 + 7, 5 + 7 -5가 계산되는데 이때, 10 - 5 + 7을 계산하기 위해서는 (10 - 5) + 7이든 10 - (5 + 7)이든 두가지가 가능하다. 근데 10 - 5와 5 + 7은 이미 step 1에서 계산했기 때문에 계산 과정을 담은 dp 배열을 참고해서 구하게 된다.
step3도 마찬가지이다.
결국 앞에서 얻었던 결과를 재활용해서 다음 연산에 쓰기 때문에 DP인 것이다.
def solution(arr):
inf = int(1e9)
n_number = len(arr) // 2 + 1
n_op = len(arr) // 2
max_dp = [[-inf for i in range(n_number)] for j in range(n_number)]
min_dp = [[inf for i in range(n_number)] for j in range(n_number)]
for step in range(len(max_dp)):
for i in range(len(max_dp) - step):
j = i + step
if step == 0:
max_dp[i][i] = int(arr[2*i])
min_dp[i][i] = int(arr[2*i])
else:
for k in range(i, j):
if arr[2*k+1] == "+":
max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] + max_dp[k+1][j])
min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] + min_dp[k+1][j])
elif arr[2*k+1] == "-":
max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] - min_dp[k+1][j])
min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] - max_dp[k+1][j])
return max_dp[0][n_number-1]
Reference
'알고리즘 풀이' 카테고리의 다른 글
[알고리즘][X] 도둑질 (0) | 2023.07.18 |
---|---|
[알고리즘][X] 등굣길 (0) | 2023.07.17 |
[알고리즘] 정수 삼각형 (0) | 2023.07.15 |
[알고리즘][X] N으로 표현 (0) | 2023.07.14 |
[알고리즘][X] 단속카메라 (0) | 2023.07.13 |