[C언어] 2467. 용액

 

오른 차순으로 입력 받는 배열들 중 2개를 선택해 그 합이 가장 작을 때의 두 배열 인덱스를 출력하는 문제이다.

이 경우도 완전 탐색으로 2개의 용액을 다 더해보면 시간 초과가 난다. 그래서 모든 결과 값을 구하여 결과를 얻는 방법 말고 새로운 방법으로 문제를 풀어야 한다.

 

오름차순으로 정렬되어 있다는 것을 기반으로 좀만 더 생각해보면, 우리는 이것을 시간복잡도 N으로 풀수 있다.

 

변수 및 배열 선언

문제에서 주어진 범위가 -10억~10억. int의 범위 대략 -21억~21억
문제에서 알칼리만 -10억짜리 2개이면 -20억, 산성 +10억짜리 2개이면 +20억으로
int의 범위안에 들어온다. long long을 쓸 필요가 없다.

 

N개의 입력 받은 배열 arr의 0번 인덱스와 N-1인덱스 번호를 저장하고 있는 두 개의 변수를 선언한다.

그리고 해당 배열의 합을 비교해나가는 방식이다.

나는 처음 0번 인덱스를 저장하는 변수를 S, 마지막 N-1을 저장하는 변수를 E로 선언하였다.

 

S와 E 변수의 증감

두 배열의 합이 -이면 0에 가깝게 하기 위해 더 작은 알칼리성 용액으로 더해주어야 한다.

그래서 이 경우 한 칸 오른쪽의 인덱스의 배열의 값으로 계산해 주어야 하기 때문에 S++해준다.

 

두 배열의 합이 +이면 0에 가깝게 하기 위해 더 작은 산성 용액으로 더해주어야 한다.

그래서 이 경우 한 칸 왼쪽의 인덱스의 배열의 값으로 계산해 주어야 하기 때문에 E--해준다.

 

http://colorscripter.com/s/65gBM51