Red Salmon

출처 : 코드그라운드

정답 : 링크

이 문제의 경우 지그재그 매트릭스를 만드는 것이다. 과거에도 몇번 풀어봤던 유형인데 그때마다 햇갈려한다. 

이런문제는 당연히 배열을 만들어서 값을 채워넣고 출력하라는 말은 절대 아니다. 수식을 만들어서 계산하라는 의미이다.

먼저 수식을 만드는 방법은 참 많이 있을것이고 나보다 더 훌륭한 방법이 분명 있을것이지만 난 나의 방식대로 하였다.

접근 방법

1. 우선적으로 지그재그 이동방향은 좌표값으로 알 수 있다. 왼쪽 상단을 (1, 1)이라고 할 때, x+y-1을 하여 2로 나눈값이 홀수이냐 짝수이냐에 따라 왼쪽에서 오른쪽으로 커져가는지 오른쪽에서 왼쪽으로 커져가는지 알 수 있다.

2. 모든 좌표를 그대로 이동하였을때 왼쪽끝으로 오면 어떤수인지 알아내고자 한다. 그 후에 해당 좌표만큼 더해주거나 빼주면 끝인 것이다. 이때 배열을 반으로 나눠야 한다. 

   그 이유는 반으로 커져갈때는 일정한 규칙성을 가지지만 반이 끝났을때는 계속 줄어들게 되므로 규칙성이 깨지게 된다. 그러므로 반으로 나눠서 계산한다.

3. 수식을 찾는다. 수식은 개인적으로 경험을 토대로 유추해봤다.

val = 1 + (temp - 1) / 2 + odd[((temp - 1) - (temp - 1) / 2) - 1];

위와 같은 규칙을 가지게 되는데 temp는 x+y-1로 정의를 하고 있다. 이 규칙을 도입하면 왼쪽 에 어떤수가 위치하는지 알 수 있다. odd배열은 상단에 만들어 놨는데, 규칙에 따라서 수가 증가됨을 알기에 미리 만들어놓는다. 물론 이 수식마저 배열로써 규정시킬 수 있다.

4. 값이 왼쪽으로 뻣어나갈때 왼쪽끝이 아니라 하단에 위치하게 된다면 새로운 수식을 도입해야 한다. 필자는 수식을 만들다가 굳이 그럴 필요가 없지 않을까? 시간상으로 충분할 것 같은 생각이 들어 한번에 배열로써 만들고 계산하고자 하였다. 코드상의 22번째 라인부터 44번째 라인이 그 부분이다. 미리 배열로써 증가하는 규칙에 맞춰 배열을 한번에 만들어놓았다.

5. 다 구해졌으니 이제 왼쪽으로 뻣어나간 값에서 해당 좌표값을 빼거나 더해서 값을 구하고 더한다. 

이런 문제는 수식을 찾으라는 문제인데, 수식은 솔직히 그날의 컨디션이 중요한거같다. 

잘풀릴때는 한번에 찾아지지만 못찾을때는 정말 안찾아진다. 이 문제는 비교적 빠르게 찾은것 같다.  

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

정답 : 링크

버전을 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도 포함을 해야 한다. 중복으로 더할수도 있기 때문이다.

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