[코이] 용액

IOI korea 공식 유튜브 영상 링크

https://www.youtube.com/watch?v=iSjvuixMPmQ

 

문제 링크

https://www.codeup.kr/problem.php?id=4696 <-- CodeUp

http://koistudy.net/?mid=prob_page&NO=399&SEARCH=0 <-- KOISTUDY

https://www.acmicpc.net/problem/2467 <-- BAEKJOON

 

목차

1. 문제 접근 방법

2. native ( TLE )

3. Two pointers algorithm ( AC )

 

문제 접근 방법

두 개의 수를 더한 값이 0에 제일 가깝도록 하는 두 수를 구하는 문제이다.

 

처음 해야 할 것은? 두 값을 어떻게 이동시킬 것인지 생각해 주어야 한다.

두 값의 위치를 0과 1로 잡았을 때, fp(first point)와 ep(end point)가 n이 될 때까지 증가 시키면서 값을 계산하면 O(n^2)에 푸는 것과 다를 것이 없다. 오히려 계산량의 차이도 얼마 느껴지지 않을 수도 있다. 그래서 글쓴이는 양 끝값을 fp와 ep로 잡고 조건에 따라 위치를 옮기며 연산하는 Two pointers algorithm을 사용할 생각을 하였다.

 

그 다음으로는 두 지점을 어떤 규칙을 통해 이동시킬 것인지를 생각해주어야 한다.

Two pointers algorithm을 사용하는데 만약 두 지점의 수의 합이 0보다 크다면 0보다 무조건 큰 것이므로 이를 줄여주기 위해 양의 값을 0쪽으로 움직여주어야 한다. 아니라면 음수를 양의 방향으로 옮겨주어야 한다.

 

이를 점화식으로 나타내주면 다음과 같이 나타내 줄 수 있다.

ep-1 ( a[ fp ]+a[ ep ] > 0 )

fp+1 ( else )

 

마지막으로는, 0에 가까운 수라는 것을 어떻게 판별할 것인지를 생각해 주어야 한다.

글쓴이는 절댓값을 이용했는데, 그 이유는 음의 정수와 양의 정수를 비교할 때, 거리를 비교하는 것이라면 |-k|나 k나 0으로부터 거리는 같기 때문이다. 이렇게 해서 거리를 비교해 주었다면, 그 다음으로는 당연히 이것이 최소 거리인지를 판별해서 만약 최소 거리라면 거리의 값을 갱신해 주어야 한다.

 

Native

#include <cstdio>
#include <vector>
using namespace std;

int n, sa, sb, M = 2000000000;
vector<int> V;

int abs(int k) { return k>=0?k:-k; }

int main()
{
  scanf("%d", &n);
  for(int i=0, t; i<n; i++){
    scanf("%d", &t);
    V.push_back(t);
  }

  for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
      if(abs(V[i]+V[j]) <= M){
        M = abs(V[i]+V[j]);
        sa = V[i];
        sb = V[j];
      }

  printf("%d %d",  sa, sb);

  return 0;
}

이 문제의 경우에도 배열 범위가 10만인데 O(n^2)을 돌리면 100억이 넘어버리는 연산을 해 버려 시간초과가 날 수 밖에 없는 구조이다. 따라서 다음 코드를 이해하고 열심히 짜 보자!

 

Two pointers algorithm

#include <cstdio>
#include <vector>
using namespace std;

int n, fp, ep, sa, sb, M = 2000000000;
vector<int> V;

int abs(int k) { return k>=0?k:-k; }

int main()
{
  scanf("%d", &n);
  for(int i=0, t; i<n; i++){
    scanf("%d", &t);
    V.push_back(t);
  }

  fp = 0;
  ep = V.size()-1;

  while(fp != ep){
    if(M >= abs(V[fp]+V[ep])){
      sa = V[fp];
      sb = V[ep];
      M = abs(V[fp]+V[ep]);
    }
    if(V[fp] + V[ep] > 0) ep--;
    else fp++;
  }

  printf("%d %d",  sa, sb);

  return 0;
}

최대를 20억으로 잡은 이유는?

- 입력되는 변수의 크기가 최대 10억인데, 두 포인터가 모두 10억을 가리킬 경우에 더하면 20억이 되기 때문이다.

  예상 체점 데이터

  5

  10억 10억 10억 10억 10억

  체점데이터는 우리에게 관대하지 않기 때문에 이런 최대 경우를 생각해 주지 않으면 에러가 나기 쉽다.