Red Salmon

문제  : 코드그라운드 좋은수

정답 : 링크

버전을 2개나 만들었다. 첫번째 버전은 이유는 모르겠으나 0점이 나와서 알고리즘 전체를 변경하기로 하였다.

방법 자체는 동일하다.

먼저 코드그라운드 문제의 특징은 테스트케이스가 여러개인데 이 모든게 제한시간내에 작동해야한다.

BOJ의 경우 케이스당 제한시간인거와 비교하면 다른 방식이다. 

물론 ACM-ICPC도 코드그라운드와 동일하다. 대신 제한시간이 보통 3초이다.

문제의 기본 틀은 다음과 같다.

1. 먼저 2중포문을 통해 숫자 2개의 합을 구한다.  chk 배열을 만들고 체크한다.

2. 현재수 = 이전 3개의 수의 합이다. 즉, 어떤 수 + 1에서 구한 2개의 수가 현재수와 같다면 이는 가능한 경우로 본다. 이 처리를 chk[현재수 - 어떤수]가 참이라면 가능한것이다. 

이 기본틀만 유지하면 된다. 이를 가지고 어떻게 코딩하든 답은 나와야 하는것이다. 틀렸다면 뭐 예상치못하는 문제가 있는것일거라고 생각한다.

그래서 나는 다음과 같은 로직을 세웠다.

1. 40만의 배열을 만든다. (한개 수의 입력 최대는 절대값 10만이다. 음수까지고려하면 20만이되고 나는 2개 수의 합을 구하려 하기 때문에 최대 40만이 된다는 가정을 둔다.)

2. 입력 포문을 만들고 바로 아래 합이 가능한지 확인하는 포문을 둔다. 확인은 다음과 같다. 
    chk[200000+arr[i]-arr[k]]이다. 20만은 쉽게 생각해 0이라고 보면 된다. 이게 음수가 될 수 있기 때문이다. 이는 결과적으로 현재수에 어떤수를 뺐는데 그 수가 이미 체크가 되어있다면 2개의 수로 만든 경우가 되는 것이다. 그러므로 ++를 해주고 바로 브레이크 처리를 한다. 중복을 피해야하기 때문이다.

3. 2개의 수의 합을 체크하는 포문을 하나 둔다. i도 포함을 해야 한다. 중복으로 더할수도 있기 때문이다.

이렇게 쓰니 참 간단한데, 생각하기 까지 참 오래시간이 걸렸다. 너무오랜만에 코딩을 한 것같다.