Red Salmon

출처 : https://www.acmicpc.net/problem/1587

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/1587.cpp

음..나는 이분매칭을 공부하려고 이문제를 열었으나, 이 문제는 이분매칭과는 조금 거리가 있어보인다.

풀이도 전혀 상관없어보인다.

문제가 상당히 어렵게 풀어져있는데 핵심은 매우 간단한 것이다. 하지만 나는 찾지 못하였고 구글링을 통해 문제를 이해하였다.

접근방법

1. 우선 A라는 집합안에서도 매칭이 가능하다. 그리고 답은 최대 매칭을 구하는 것이다. 그렇다면 기본적으로 각 집합을 2로나눈 값을 더한게 최대 매칭이 된다. (하단에 위치한 연결간선은 최대매칭을 해봐도 집합안에서 하는것보다 작게 나온다.)

2. 만약 A또는 B 둘 중 하나가 홀수고 하나는 짝수라면 결국 한녀석은 마지막까지 선택이 되지 않으므로 무시한다.

3. 하지만 둘다 홀수라면 2개씩 짝지어도 하나씩 남는다. 여기서 만약 하단에 입력으로 홀수에서 홀수로가는 간선이 하나라도 존재하면 모두 연결이 되는 것이고, 홀수에서 짝수로만 가거나 짝수에서 짝수로만 가게 된다면 결국 남게 되는 것이다. 그래서 모두 연결되었을때 +1을 해주면 답이 나온다.

예시를 들어보겠다.

A 가 3이고 B가 3이라고 가정하자.

하단의 매칭 부분에서 1->3 혹은 1->1 혹은 3->3 이 존재하면 +1의 경우가 생기는 것이고 나머지 녀석들은 볼필요도없이 나누기 2를 하면 매칭수가 나오게 된다. 

그런데 만약 연결이 1->2 혹은 3->2 혹은 2-> 모든수 라면 동일 집합에서 연결할수 있는 경우가 사라지게 된다. 문제에서 분명 연속된 수끼리만 연결이 된다고 하였으니 불가한 경우가 된다. 다음의 문장을 명심해야한다.

거의 이분 그래프는 이분 그래프와 다르게 nA-1 + nB-1개의 간선을 추가로 가진다. 추가가 되는 간선은 Ai에서 Ai+1로 가는 간선 (1 ≤ i ≤ nA-1)과 Bi에서 Bi+1로 가는 간선 (1 ≤ i ≤ nB-1)이다.

위 문장에 따라 연결이 끈기게 되므로 필요가 없어진다. 그래서 반드시 홀수끼리 연결이 되야 한다. 

실로 간단한 문제이나, 문제가 어렵게 설명된거 같은 느낌이다.

출처 : 코드그라운드

정답 : 링크

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

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

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

접근 방법

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

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

출처 : https://www.acmicpc.net/problem/2240

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/2240.cpp

이 문제 역시 DP로 풀 수있다. 처음에는 DFS가 될까? 생각하였지만 아무리 계산해봐도 시간복잡도에서 초과가 되어버린다. 왜냐면 T가 1000이기 때문에 DFS로는 가망성이 없다.

그럼 결국  DP인데, 매 초마다 최대값을 갱신하는 방식을 써야겠다. 

개인적으로 상당히 고생했던 DP이고 결국 풀지못하여 다른사람의 아이디어를 참조했다.

이 DP문제의 경우 숫자로 가지고있는 패턴은 당연히 없고(n이 몇일때 몇이다가 아니다.), 배열로 맞추는 패턴도 아닌것같기 때문이다.

정답자의 아이디어를 빌리면 다음과 같다.

1. 나무의 위치를 입력받음에 따라 스텝수에 따라 해당 위치값을 1씩 더해준다. (이동할수있는 만큼 계속 이동한다고 전제하면 현재 위치에서 얻은 값은 계속 가져갈수있다.)

2. 현재 위치에서 바로 전의 단계에서 옆나무의 포인트를 보고 큰값을 대입한다. (이동을 안 할수도있는것이다.)

3. 최종적으로 담겨있는 가장 큰 값을 출력한다.

참으로 심플한 아이디어이다.  이렇게하면 각 스텝별로 얻을수있는 최고점수를 바로 알 수있다. 정말 신박한 아이디어라고 생각한다.