미소를뿌리는감자의 코딩
[백준 2024/09/19] 14888번 연산자 끼워넣기 본문
728x90
1. 문제
https://www.acmicpc.net/problem/14888
2. 접근 방법
어떻게 연산자들의 경우의 수를 표현할 수 있을까 고민해 보았다.
처음에 잘 생각이 나지 않았지만, 섣불리 접근하다간 오히려 시간을 많이 쓸 것 같아서 더 고민해 보았다. - 요런 태도가 코테에서는 중요한 것 같다. (메모메모~)
예를 들어
+ : 2개
- : 1개
* : 1개
/ : 1개
라면,
+가 중복 되기에, 중복 case를 제외시켜 주어야 한다.
따라서, dfs를 이용해서
dfs(현재 연산 경우의 리스트, 사용하고 남은 연산자 리스트) 로 문제 풀이를 시작한다.
만약, 현재 연산자 경우의 리스트의 len이 연산자 개수라면, 해당 리스트를 total 에 append하고 return 한다.
그 외는 for i in range(4)를 하면서, 특정 연산자가 남았다면, cur_list에 append 하고, 사용한 연산자를 뺀 리스트를 다시 넣어준다.
ex)
만약 연산자를 [2, 1, 1, 1]로 넘겨주었고, +를 사용하였다면 다음 dfs로는 ([1], [1, 1, 1, 1]) 을 넘겨주면 된다.
이렇게 만든 연산자 경우의 수를 가지고, 계산을 진행하면 된다. -> 여기서 시간 초과가 나지 않을까 걱정을 했지만 다행히 나지 않았다.
만약 시간 초과가 났다면, memoization 사용 여부를 고려했을 것 같다.
3. 코드
def dfs(cur, left):
if len(cur) == num_cnt - 1:
total.append(cur)
return
for i in range(4):
if left[i] > 0:
left[i] -= 1
dfs(cur+[i], left)
left[i] += 1
def op_calculate(nums, total):
values = []
base_num = nums.pop(0)
for t in total:
value = base_num
for i in range(num_cnt - 1):
if t[i] == 0:
value += nums[i]
continue
elif t[i] == 1:
value -= nums[i]
continue
elif t[i] == 2:
value *= nums[i]
continue
else:
if value < 0:
value *= -1
value = value // nums[i]
value *= -1
continue
value = value // nums[i]
values.append(value)
return min(values), max(values)
if __name__ == "__main__":
num_cnt = int(input())
nums = list(map(int, input().split()))
op = list(map(int, input().split()))
total = []
dfs([], op)
min_v, max_v = op_calculate(nums, total)
print(max_v)
print(min_v)
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/09/20] 2617번 구슬 찾기 (1) | 2024.09.20 |
---|---|
[백준 2024/09/20] 2573번 빙산 (0) | 2024.09.20 |
[백준 2024/09/19] 21606번 아침 산책 (0) | 2024.09.19 |
[백준 2024/09/18] 1707번 이분 그래프 (0) | 2024.09.18 |
[백준 2024/09/17] 5639번 이진 검색 트리 (0) | 2024.09.17 |