🧩 Problem Solving
[BOJ] 백준 2467, 2473번 : 용액, 세 용액
date
May 30, 2023
slug
boj-2467-2473
author
status
Public
category
🧩 Problem Solving
tags
BOJ
summary
투포인터, 3-SUM
type
Post
thumbnail
문제링크
2467번: 용액
투포인터 사용하는 문제
- 수열에서 특정한 합을 가지는 부분 연속 수열을 찾을 때 투포인터 사용함
구현
정렬 후 양 끝에서 포인터를 이동하며 0에 가까운 값 찾기
필요 데이터 or 변수
- M = 찾고자 하는 부분 연속 수열의 합
- cnt = 부분 연속 수열의 개수를 나타내는 변수
- sum = 현재 부분합 저장하는 변수(이 문제의 경우 부분합이라기보단 두 포인터가 가르키고 있는 각 용액의 합)
- start, end = 포인터 변수
- 배열 혹은 리스트 오름차순 정렬
- 현재 부분합(sum)과 목표합(M)을 비교하며 포인터 이동
- 부분합이 M보다 크다면 a+b 의 값을 더 줄여야 하므로 b 값을 내리기
- 부분합이 M보다 작다면 a+b 의 값을 더 키워야 하므로 a 값을 올리기
- 부분합이 M과 같다면 카운트
⇒ O(N)의 시간복잡도로 탐색 가능!
2473번: 세 용액
투포인터 + 3-SUM
하나의 값을 고정한 후(N) 투포인터 진행(N)
O(N*N)의 시간복잡도로 탐색 가능