[Algorithm] 2295. 세 수의 합

유지민·2024년 3월 27일
0

Algorithm

목록 보기
65/75
post-thumbnail

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로 누적합을 계산하는 것이 아니라, 이분탐색을 적용해 문제를 푸는 방식으로 다시 시도했다.

배운점 또는 느낀점

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

profile
끊임없이 도전하며 사고하는 주니어 Web 개발자 유지민입니다.

0개의 댓글