-
[백준 2473번] 세 용액백준 알고리즘 2019. 2. 23. 20:06
BOJ 2473번
https://www.acmicpc.net/problem/2473
백준 2473번 C++ 소스
브루트포스로 i, j, k 변수 선언하고 3중 for문으로 풀려고 했었으나, 그렇게 되면 N^3 이라
시간초과가 날 수 밖에 없다.
https://en.wikipedia.org/wiki/3SUM 에 힌트가 있었다.
fix라는 변수를 이용해서 하나를 딱 정한다음에 start와 end를 이용해서 점점 조여오는 방법이다.
i) 3개의 수 합이 0보다 클 경우 0에 가깝기 만들기 위해 end를 하나 줄여서 작은수를 대입시킨다.
ii) 3개의 수 합이 0보다 작을 경우 0에 가깝기 만들기 위해 start를 하나 늘려서 큰 수를 대입시킨다.
iii) i, ii 의 경우에 모두 해당하지 않는 경우는 0이므로 i=N으로 두어 for (i = 0; i < N - 2; i++) 반복문을 탈출하게 하고 while(true) 반복문도 역시 빠져나온다.
입력받은 배열 arr를 이미 오름차순으로 정렬해두었기 때문에 위 3가지 방법이 쉽게 가능하게 된 것이다.
start와 end를 조절하면서 total값과 현재의 3개 수 절대값 합을 비교해본다.
만약 현재의 3개 수 절대값 합이 더 작으면 해당하는 그 index를 기억하기 위해
a, b, c변수에 저장하고 아니라면 그냥 skip한다.
start와 end값이 같아지면 while문을 빠져나오고 fix를 하나 올리고 다시 과정을 반복하는 코드이다.
사용했던 테스트 케이스
소스코드
#include "pch.h" #include <iostream> #include <cmath> #include <string> #include <algorithm> using namespace std; int main(void) { long long arr[5001], total = 9223372036854775807; int N; int i; int fix, start, end; int a, b, c; cin >> N; for (i = 0; i < N; i++) { cin >> arr[i]; } sort(arr, arr + N); for (i = 0; i < N - 2; i++) { fix = i; start = fix + 1; end = N - 1; while (true) { if (start == end) break; if (abs(arr[fix] + arr[start] + arr[end]) < total) { a = i; b = start; c = end; } total = min(total, abs(arr[fix] + arr[start] + arr[end])); if (arr[fix] + arr[start] + arr[end] > 0) { end--; } else if (arr[fix] + arr[start] + arr[end] < 0) { start++; } else { i = N; break; } } } cout << arr[a] << ' ' << arr[b] << ' ' << arr[c] << endl; return 0; }
개발환경 및 컴파일 기준은 visual studio community 2017
'백준 알고리즘' 카테고리의 다른 글
[백준 1010번] 다리 놓기 (2) 2019.03.03 [백준 10844번] 쉬운 계단 수 (0) 2019.02.28 [백준 1018번] 체스판 다시 칠하기 (0) 2019.02.25 [백준 1912번] 연속합 (0) 2019.02.25 댓글