문제 링크
https://www.acmicpc.net/problem/3151
미해결
- 풀이시간 : 2시간 이상
- 오답 이유 : 제일 큰 이유는 설계를 안해놓고 또 아는 문제라고 쑤신게 아닌가 싶다. 3개를 찾아내는 이분탐색 문제를 '세 용액'문제로 해결해 본적이 있기에 하나의 항을 고정해놓고 두개를 이동시키며 이를 해결하고자 했으나 중복된 원소가 있다는 다른 점을 캐치해내지 못했다. 이것이 오답의 시작인 가장 큰 이유다.
- 이 하나의 시작점 : 중복된 원소가 있다는 점을 알고 나서도 새로운 문제라고 생각하지 않고 계속 들쑤시다가 결국에 방법을 찾지 못했다. 아는 문제라고 생각하면 처음 부터 설계 하지 않고 기존의 풀이에서부터 조금씩만 뜯어서 정답을 맞추려고 하는게 가장 큰 문제인 듯 싶다.
- 왜 생각하지 못했는가? : 두개의 항을 조절하면서 중복된 항을 처리할 방법을 여러가지 고민해 보았다. 동시에 이동도 시켜보기도 하고 각 갯수를 구해서 곱하는 방법을 적용시켜보기도 하였다. 동시에 이동시키려고 했던 것이다. 그렇기에 한쪽을 고정하면서 다른쪽만 구하는 방법을 또 생각해내지 못했다. 왜 생각하지 못했는가? 순차적으로 접근하지 못했는가? 한쪽이 다른 한쪽에 영향을 받는 케이스, 즉 두개가 같은 것을 분리해내면 되는 방법을 생각을 하지 않은 것이다. 이 케이스를 분리해내는 방법을 고려했다면 풀었을지도 모른다. 동시성이 있을 때, 두개다 전부 제어가 되지 않는다면 한쪽을 고정하는 방법을 사용해야 한다는 점을 깨달았다. 한쪽이 고정이 되지 않는다면 한쪽이 고정이 되지 않는 케이스를 분리해내는 것이다. 즉, 최대한 이분화해서 떼어내려는 습관이 필요할 거 같다. 동시에 안되는걸 계속해서 동시에 해보려는 접근방식의 문제였다.
🕒 Python 풀이시간: x
from bisect import bisect_left
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
answer = 0
for i in range(len(arr)-2):
left, right = i+1, N-1
while left < right:
result = arr[i]+arr[left]+arr[right]
if result > 0:
right -= 1
else:
if result == 0:
if arr[left] == arr[right]:
answer += right - left
else:
idx = bisect_left(arr, arr[right])
answer += right-idx+1
left += 1
print(answer)이렇게 Python으로 백준의 "합이 0" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
