문제
- 2467번 : 용액
- Rank : gold V
- https://www.acmicpc.net/problem/2467
2467번: 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -
www.acmicpc.net
풀이 전략
- 2중 for문을 사용할 경우에는 O(N^N)이 되게 되어 시간 초과에 걸리게 된다.
- 입력값이 오름차순으로 입력되는것을 이용하여, 인덱스 두개를 사용하여 계산한다.
- 양쪽 끝에 각 인덱스를 둔 다음, 두 용액의 합이 양수라면 오른쪽 인덱스를, 음수라면 왼쪽 인덱스를 한 칸 중앙으로 당긴다.
- 해당 계산은 두 인덱스가 겹치거나, 두 용액의 합이 0이 될 경우 종료한다.
- 0에 가장 가까운 용액합이 나왔을 경우 인덱스를 저장해뒀다가, 정답으로 출력한다.
EX)
-7 -4 3 6 9 -> -7 + 9 = 4 < 0 : 9를 6으로 옮긴다
-7 -4 3 6 9 -> -7 + 6 = -1 > 0 : -7를 -4으로 옮긴다
전체 소스 코드
더보기
//Backjoon Problem No.2467
//https://www.acmicpc.net/problem/2467
#include <iostream>
using namespace std;
int main()
{
int N;
int liquids[100000] = { 0, };
int idxA, idxB;
int minValue = 2000000001;
int answerA, answerB;
//입출력 속도 증가
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++)
cin >> liquids[i];
idxA = 0;
idxB = N - 1;
while (idxA != idxB)
{
int temp;
temp = liquids[idxA] + liquids[idxB];
if (temp > 0)
{
if (temp < minValue)
{
minValue = temp;
answerA = liquids[idxA];
answerB = liquids[idxB];
}
idxB--;
}
else if (temp < 0)
{
temp = temp * -1;
if (temp < minValue)
{
minValue = temp;
answerA = liquids[idxA];
answerB = liquids[idxB];
}
idxA++;
}
else
{
minValue = 0;
answerA = liquids[idxA];
answerB = liquids[idxB];
break;
}
}
cout << answerA << " " << answerB;
return 0;
}
'Problem Solving > Backjoon' 카테고리의 다른 글
| [백준][C++]9465 - 스티커 (0) | 2022.03.14 |
|---|---|
| [백준][C++]1036 - 36진수 (0) | 2022.03.08 |
| [백준][C++]1562 - 계단 수 (0) | 2022.03.08 |
| [백준][C++]1043 - 거짓말 (0) | 2022.03.03 |
| [백준][C++]9663 - N-Queen (0) | 2022.03.02 |