[백준 / BOJ] 1253 좋다

문제

출처 : www.acmicpc.net/problem/1253

1253번: 좋다

N개의 수열이 주어진다.

이때, N개의 수 중에서, 어떤 수가 다른 수 두개의 합으로 나타내진다면, 그 수를 좋다 라고한다. 

좋은수가 몇개인지 구하는 문제다.

(위치가 다르면 값이 같아도 다른 수 이다.)

 

풀이

완전탐색으로 풀경우 O(N^3)이 되어서 시간초과가 난다. 시간초과를 피하기 위해, 이분탐색으로 풀은 문제다.

 

로직은 간단한데,

수열 N에서 i번째수를 Ni라 할때,

 

1. 좋은 수 인지 판단할 수 Ni를 하나 지정한다.

 

2. Ni에 Nj를 뺀다. (i != j)

 

3. 수열에서 Ni-Nj가 있는지 이분탐색으로 찾는다.(수열 N은 정렬되어있다고 가정)

 

4. 만약 있다면, Ni는 좋은수다.

 

예외처리를 해주는것이 까다로웠다.

3가지 예외상황이 있었는데,

 

1. Ni == 0, Nj == 0 인 경우 (Ni - Nj == Ni && Ni - Nj == Nj)

-> 0의 경우 0에 자기자신을 빼면 0 이된다. 즉, (Ni - Nj == Ni && Ni - Nj == N) 경우이다.

이 경우 0의 갯수가 3개 이상일때만 좋은 수 이다.

수열이 다음과 같다고 하자.

2

0 0

예외 처리를 해주지않으면, 2를 답으로 반환 할 것이다. 0은 2개밖에 없으므로 절대 좋은 수가 될수없다.

3

0 0 0

예외처리가 잘 되었다면 위 수열에 대해 3이 출력되어야한다.

 

2. Nj == 0 인 경우

-> Nj가 0이라면, Ni의 갯수가 2개 이상일때만 체크해줘야한다.

3

0 1 2

의 경우에서 예외처리를 해주지 않는다면, 2를 출력할것이다.

2의 경우 2 - 0 = 2 에서 2가 수열에 있다고 리턴하기때문에 좋은 수가 되고, 1또한 마찬가지로 좋은 수가 된다.

 

 

3. Ni - Nj == Nj 일경우

-> 이 경우, Nj의 갯수가 2개 이상일때만 좋은 수 이다.

예를들어, 수열이 다음과 같다고 하자.

5

1 2 2 2 2

예외처리를 해주지않는다면 답을 4로 반환할것이다.

2 - 1 = 1 이고, 수열에는 1이 존재하므로, 답을 4로 반환할것이다. 하지만 이 경우, 1 이 중복으로 사용된것이라 2는 좋은 수가 될수없다.

따라서, 1이 2개 이상인경우만 답으로 체크해줘야한다.

 

위 3가지 경우를 예외처리해주고 맞았습니다를 맞았다.

 

 

(탐색 을 빠르게 하기위해 각 수의 첫 등장위치와 마지막위치를 저장해주고, 해당 수가 좋은 수 라면, 마지막위치 - 첫 등장위치 + 1 만큼 좋은수 처리를 해주며 i를 첫 등장위치로 바로 넘겨줬다.)

 

=========================

 

 

다음은 내가 틀려가며 만든 반례들이다.

 

3

-3 0 3

답 : 1 (0 만 좋은수가 됨)

 

2

0 0

답 : 0 (좋은수가 있을 수 없음)

 

3

0 0 0

답 : 3 (모두 좋은 수임)

 

3

0 1 1

답 : 2 (1만 좋은수임)

 

3

0 0 1

답 : 0 (좋은 수가 없음)

 

5

-2 -1 -1

답 : 1 (-2가 좋은 수임)

원래 로직은 정렬되어있는 N을 i-1위치부터 이분탐색을 시작했었다.

(A를 두개 의 합으로 나타내는경우 합치는수는 항상 A보다 작을거라 생각했었기때문에.....)

이럴 경우 -2 = -1 + -1경우를 봐주지 못한다.

(-1은 -2보다 더 크지만, -2가 좋은 수 인지 판단할때 -1을 체크하지않음..)

 

(처음엔 깨끗했던 코드가..10번째 재출부터 더러워 지기 시작했다....)

 

음수와 0에서 예외상황을 처리해주는것이 중요했던 문제였다. 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1253%20%EC%A2%8B%EB%8B%A4/main.cpp

devxb/JJUNalgo