[알고리즘][2][RE] 사칙연산
2023. 8. 23. 13:10ㆍ알고리즘 풀이
문제 설명
사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 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를 for문에서 사용할 때는 중간 연산자가 이미 계산된 적이 있도록 즉 쌓아지도록 설계해야 한다는 것을 배웠다.
- 처음에는 [1][2] [1][3] [1][4] 이렇게 했는데 이렇게 되면 [1][4]를 계산할 때 필요한 [1][2][2] 등은 아직 계산이 되지 않은 상태이다.
- for문 순서가 헷갈리긴 한다. 순서를 아무렇게 해도 되는지 아니면 저렇게 해야 하는지
import math
def solution(arr):
# 최대를 구하는 문제이므로 그리디, DP, 탐색
# 항상 최선의 선택을 할 수는 없으므로 그리디 X
# 그래프 탐색을 하려면 만약 101개의 숫자가 있다고 한다면 (1, 100), (2, 99), (3, 98) ... 이고 그 안에서도
# (1, (1, 99)), (1, (99, 1)) 등 나누어지므로 ! 단위가 되기 때문에 힘들다.
# 그러나 중간 연산을 계속 활용하기 때문에 DP를 활용하면 된다.
# 4개인 경우를 생각해보자
# (1, 3), (2, 2), (3, 1)
# (1, (1, 2)) (1, (2, 1)), ((1, 1), (1, 1)), ((2, 1), 1), ((1, 2), 1)
# (1, (1, (1, 1))), (1, ((1,1), 1)) ((1, 1), (1, 1)), (((1, 1), 1), 1), ((1, (1, 1)), 1)
# f(4)에 최댓값이 담겨 있기 위해서는 (1, 3), (2, 2), (3, 1) 중 가장 큰 값을 선택해야 한다.
# 또한 각각은 ,가 -라면 앞은 최대, 뒤는 최소, ,가 +라면 앞은 최대, 뒤도 최대가 되어야 한다.
# 따라서 최대 DP, 최소 DP를 운영해야 한다.
# 12 23 34 13 24 14
# max_dp[i][j]는 i부터 j까지의 최댓값
max_dp = [[-float(math.inf)] * ((len(arr)//2)+2) for _ in range((len(arr)//2)+2)]
min_dp = [[float(math.inf)] * ((len(arr)//2)+2) for _ in range((len(arr)//2)+2)]
for i in range(1, (len(arr)//2)+2):
max_dp[i][i] = int(arr[2*(i-1)])
min_dp[i][i] = int(arr[2*(i-1)])
for j in range(1, (len(arr)//2)+2):
for i in range(1, (len(arr)//2)+2):
for k in range(1, i+j):
if i+j >= (len(arr)//2)+2:
continue
if arr[2 * k - 1] == "+":
max_dp[i][i+j] = max(max_dp[i][i+j], max_dp[i][k] + max_dp[k+1][i+j])
min_dp[i][i+j] = min(min_dp[i][i+j], min_dp[i][k] + min_dp[k+1][i+j])
elif arr[2 * k - 1] == "-":
max_dp[i][i+j] = max(max_dp[i][i+j], max_dp[i][k] - min_dp[k+1][i+j])
min_dp[i][i+j] = min(min_dp[i][i+j], min_dp[i][k] - max_dp[k+1][i+j])
return max_dp[1][-1]
이 코드는 리팩토링한 코드
import math
def solution(arr):
# 최대를 구하는 문제이므로 그리디, DP, 탐색
# 항상 최선의 선택을 할 수는 없으므로 그리디 X
# 그래프 탐색을 하려면 만약 101개의 숫자가 있다고 한다면 (1, 100), (2, 99), (3, 98) ... 이고 그 안에서도
# (1, (1, 99)), (1, (99, 1)) 등 나누어지므로 ! 단위가 되기 때문에 힘들다.
# 그러나 중간 연산을 계속 활용하기 때문에 DP를 활용하면 된다.
# 4개인 경우를 생각해보자
# (1, 3), (2, 2), (3, 1)
# (1, (1, 2)) (1, (2, 1)), ((1, 1), (1, 1)), ((2, 1), 1), ((1, 2), 1)
# (1, (1, (1, 1))), (1, ((1,1), 1)) ((1, 1), (1, 1)), (((1, 1), 1), 1), ((1, (1, 1)), 1)
# f(4)에 최댓값이 담겨 있기 위해서는 (1, 3), (2, 2), (3, 1) 중 가장 큰 값을 선택해야 한다.
# 또한 각각은 ,가 -라면 앞은 최대, 뒤는 최소, ,가 +라면 앞은 최대, 뒤도 최대가 되어야 한다.
# 따라서 최대 DP, 최소 DP를 운영해야 한다.
# 12 23 34 13 24 14
# max_dp[i][j]는 i부터 j까지의 최댓값
n = len(arr)//2 + 2
max_dp = [[-float(math.inf)] * n for _ in range(n)]
min_dp = [[float(math.inf)] * n for _ in range(n)]
for i in range(1, n):
max_dp[i][i] = int(arr[2*(i-1)])
min_dp[i][i] = int(arr[2*(i-1)])
for j in range(1, n):
for i in range(1, n):
for k in range(1, i+j):
if i+j >= n:
continue
if arr[2 * k - 1] == "+":
max_dp[i][i+j] = max(max_dp[i][i+j], max_dp[i][k] + max_dp[k+1][i+j])
min_dp[i][i+j] = min(min_dp[i][i+j], min_dp[i][k] + min_dp[k+1][i+j])
elif arr[2 * k - 1] == "-":
max_dp[i][i+j] = max(max_dp[i][i+j], max_dp[i][k] - min_dp[k+1][i+j])
min_dp[i][i+j] = min(min_dp[i][i+j], min_dp[i][k] - max_dp[k+1][i+j])
return max_dp[1][-1]
'알고리즘 풀이' 카테고리의 다른 글
[알고리즘][2] 아이템 줍기 (0) | 2023.08.23 |
---|---|
[알고리즘][2][X] 게임 맵 최단거리 (0) | 2023.08.23 |
[알고리즘][2][X] N으로 표현 (0) | 2023.08.22 |
[알고리즘][2] 단속카메라 (0) | 2023.08.22 |
[알고리즘][2] 큰 수 만들기 (0) | 2023.08.20 |