Red Salmon

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/7568.cpp

이 문제는 굉장히 쉽다. 그러나 나의 고질적인 문제인 대충읽기로 인해 굉장히 해맸다. 그래서 기록해야겠다고 생각했다.

 먼저 문제는 입력의 쌍이 들어오고, 여기서 덩치순위를 정하는 것이다. 나는 문제를 대충읽고, 정렬이 답이라 생각했다.

stable_sort를 통해 정렬을 시키고 바로 다음 인덱스와 크기를 비교하여 다르면 rank를 갱신하고 둘중 하나만 같으면 rank를 그대로 가는 방식으로 값을 매겼다. 물론 pos라는 값을 카운팅해주며 rank가 변할때 앞에 몇사람이 있었는지 체크하였다. 

그런데..오답을 맞았다. 직감적으로 이건 또 내가 문제를 잘못읽었겠구나 생각하며 천천히 정독하였다.  역시나..

문제에서 등급을 매기는 방법은 

 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다.

이라고 한다. 즉 정렬도 필요없고 입력받은 사람들의 데이터들을 쭉 찾으면서 자기보다 큰사람이 몇사람이나 있는지를 체크하는 것이었다. 매우 간단했다....

이런문제에 40분가량을 소요한것이 매우 우둔하며 후회스럽다. 과거 이런 습관으로 인해 큰시험에서떨어졌으면서 바뀌지 않는걸 보니 이 문제를 자각하지 못하고 있는것 같다. 쉽더라도 집중해야 한다는걸 기억하기 위해 풀이를 적었다.

출처 : https://www.acmicpc.net/problem/2505 (정확히는 정보올림피아드 문제이다.)

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2505.cpp

이 문제의 경우 정말 어렵지 않다. 다만 처음에 이렇게 생각하기가 참 힘들다. 이래서 알고리즘을 공부하나보다. 정말 역발상으로 하면 풀리는 문제였다.

우선 이 문제에 먼저 집중해야할 부분은 스페셜 저지라는 점이다. 답은 여러개라는 말이다. 

문제를 보면 입력이 주어지는데 이 입력된 수들은 2번 뒤집혔다는 말이다. 문제가 이해가 되지 않는다면 다시 읽어보면 된다.
알고리즘 공부를 한다면 문제 이해는 기본중의 기본이다. 문제가 정말 잘못되어 이해하지 못한경우라면 정답자도 없을 것이다.

암튼 나의 알고리즘은 이렇다.

1. 1 혹은 n값의 위치는 정해져있다. 즉 맨앞이거나 맨 뒤이다. 우선 여기에 초점을 맞춘다.

2. 처음엔 1을 먼저 앞으로 빼본다. 그리고 변경된 수들에서 다음 수인 2를 찾는다.

3. 2가 원래 위치와 맞는 숫자라면 다시 다음수인 3을 찾고, 틀리다면 2를 찾아서 다시 뒤집어 본다.

4. 두번 뒤집어도 값이 나오지 않으면 이번엔 맨 처음 수들에서 n값으로 찾아본다.

5. 위 과정을 다시 반복하다보면 둘중 하나에서는 반드시 정답이 나온다.

고등학생문제보니 3번 뒤집기가 있다. 이건 다르게 생각해봐야할 것 같다. 아직 풀지는 않았지만, 이 문제와는 아주 다른 해결책이 있을것이다.

정보올림피아드는 이런 방법을 허용하지 않고, 보통 비슷한 문제를 전혀다른 해결책으로 풀게 한다. 하지만 1과 n값의 위치가 포인트일것이다. 

굳이 이 수들이 앞에 있는데 뒤로 보냈다가 다시 앞으로 보내는 번거로움은 하지 않을것 같다.