알고리즘/Python 코테
99클럽 코테 스터디 9일차 TIL(dp)
집 밖은 위험해
2024. 6. 8. 15:19
📎 문제링크
https://school.programmers.co.kr/learn/courses/30/lessons/1843
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
🤔 문제 이해 및 알고리즘 유형
알고리즘 유형
DP
💡 문제 해결 방법
[프로그래머스] 사칙연산
문제 링크 [프로그래머스] 사칙연산 Link 생각의 흐름 문제에 대한 이해 DP 문제 인식 DP 구상 코드로 구현 문제의 이름은 사칙연산이지만 문제는 '+' 와 '-' 로 이루어진 더하기 빼기 문제이다. 식의
velog.io
💻 코드
def solution(arr):
nums = []
op = []
for i in arr:
if i != '+' and i!='-':
nums.append(int(i))
else:
op.append(i)
N = len(nums)
dp_min = [[float('inf')] * N for _ in range(N)]
dp_max = [[float('-inf')] * N for _ in range(N)]
for length in range(N):
for start in range(N-length):
end = start+length
if start == end:
dp_min[start][end] = dp_max[start][end] = nums[start]
continue
for mid in range(start,end):
if op[mid] == '+':
dp_min[start][end] = min(dp_min[start][mid] + dp_min[mid+1][end], dp_min[start][end])
dp_max[start][end] = max(dp_max[start][mid] + dp_max[mid+1][end], dp_max[start][end])
elif op[mid] == '-':
dp_min[start][end] = min(dp_min[start][mid] - dp_max[mid+1][end], dp_min[start][end])
dp_max[start][end] = max(dp_max[start][mid] - dp_min[mid+1][end], dp_max[start][end])
print(dp_max)
return dp_max[0][-1]👍 다른 사람 코드
def solution(arr):
arrs = ''.join(arr).split('-')
val0 = sum(list(map(int, arrs[0].split('+'))))
if len(arrs) == 1:
return val0
min_val = 0
max_val = 0
for arr in arrs[:0:-1]:
x = list(map(int, arr.split('+')))
_min_val = -(sum(x))
_max_val = sum(x[1:]) - x[0]
min_val, max_val = min(_min_val + min_val, _min_val - max_val), max(_max_val + max_val, _min_val - min_val)
return val0 + max_val✔ 생각해봐야 할 점
- 다른 사람의 풀이를 참고했는데도 이해가 잘 안된다. 과연 이문제를 나중에 스스로 생각해서 풀 수 있을지 의문이다.
- 이해할 수 있을 때까지 계속 다시 봐야겠다...