[Algorithm] 2295. 세 수의 합

2295: 세 수의 합 (이진탐색)

https://www.acmicpc.net/problem/2295

• 문제 티어 : G4
• 풀이 여부 : Failed
• 소요 시간 : 32:24

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
U = [int(input()) for _ in range(N)]
U.sort()

ans = 0
flag = True
while flag:
  check_num = U.pop() # 큰 수부터 추출

  for i in range(len(U)):
    left, right = i, len(U) - 1

    while left <= right:
      sum = U[i] + U[left] + U[right]
      if sum < check_num:
        left += 1
      elif sum > check_num:
        right -= 1
      else:
        ans = check_num
        flag = False
        break

print(ans)

접근 방식

k번째 수가 최대가 되도록 하려면, k번째는 정렬된 U 중 가장 큰 수가 될수록 좋다.
따라서 입력을 받은 뒤 U를 정렬한다.
정렬 후, 가장 큰 수부터 추출해 check_num으로 지정하며 남은 U배열을 순회한다.

for문 내부에서 left, right를 sum과 check_num의 대소관계 비교를 통해 갱신하며 가장 큰 수가 배열 내부의 세 수의 합으로 구성될 수 있을 때, 반복을 종료한다.

접근 시행착오(+ 코드)

처음에는 DP로 접근해, 배열의 누적합을 계산해놓은 뒤 구간에서의 값을 빼고자 했다.

하지만 문제 설명을 보면 {2, 3, 5, 10, 15}의 집합에서 15를 만드는 세 수의 합을 구할 때, 2+3+10으로 연속된 수가 아니어도 구할 수 있다는 예외케이스를 찾을 수 있다.

따라서 DP로 누적합을 계산하는 것이 아니라, 이분탐색을 적용해 문제를 푸는 방식으로 다시 시도했다.

배운점 또는 느낀점

이분탐색…!! 복병이다 이번주는 그리디, 이분탐색, 해시로 돌려야겠다!