Red Salmon

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

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

쉬운문제로 몸풀기용으로 풀었다. 이런건 20분내외로 풀어야 하는 문제이다.

이 문제는 당연히 배열을 만들어서 하나하나 토너먼트 시켜서 계산하라는것이 아니다.
(물론 이 문제는 그래도 답이 나올것 같다.)

단순히 패턴을 좀 보면 된다. 두사람은 만나야하며 반드시 이긴다. 토너먼트는 진행할수록 n이  반씩 줄어든다.

그러므로 둘이 만나려면 한명이 홀수 한명이 짝수여야 하며 토너먼트에서 앞서 있는 사람이 홀수여야 한다.

이 과정에 맞춰 계속 감소시켜주면 결국 만나게 되어 있고 그것을 출력하면 된다. 

뭐 설명도 필요없는 간단한 문제였다.

비주얼스튜디오 2013버전부터는 scanf를 사용 할 수 없게 막아놨다. 이유는 안전상의 문제라고 한다. 오버플루 발생 가능성때문에 안전하게 scanf_s를 사용하라고 하는데 반드시 써야할 때가 많다. 

특히 알고리즘 문제를 풀다보면 너무도 필요한 것이고, sprintf의 경우 다양한 목적으로 사용이 가능한데 spirntf_s와는 다른 결과를 내기 때문에 더더욱 필요로 한 것이다. (경험상 숫자를 문자열로 저장시킬때 사용했는데 값이 달랐다. 아니 작동하지 않았다.)

그래서 이를 다시 허가해주도록 설정하는 법을 적도록 하겠다.
(사실 내가 여기저기서 하다보니 자꾸 까먹고 검색하는게 귀찮았다.)

1. 프로젝트의 속성으로 간다. 

2. 구성속성 -> C/C++ -> preprocessor(전처리기) 로간다.

3. 다음 문장을 맨위 preprocessor Definitions(전처리기 정의)에 추가한다. 뒤에 세미콜론을 꼭 붙인다. 프로그래머에게 세미콜론은 언제나 함께하는것이다.
    _CRT_SECURE_NO_WARNINGS;

4. 확인을 누르고 실행해본다. 정상작동함을 알 수 있다.

코드상에 추가하는 방법도 있다. 

#define  _CRT_SECURE_NO_WARNINGS

그러나 나는 알고리즘 문제를 풀 뿐이니 그냥 속성을 바꾸는게 맘 편할거 같다.

출처 : 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. 다 구해졌으니 이제 왼쪽으로 뻣어나간 값에서 해당 좌표값을 빼거나 더해서 값을 구하고 더한다. 

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

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