Red Salmon

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

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

대충 보면 복잡해 보인다. 하지만 인풋에 초점을 두자. 학년은 5개 뿐이다. 학생수는 최대 1000명이다. n^2이면 1000000이고 여기에 5를 곱하니 5백만이 된다. 이정도면 무난하게 전부 조사를 해보면 될거 같다.

또한 간단히 체크하기 위해서 1000명이라고 했으니 1000 x 1000배열도 사용 가능하다는것을 알았다.

그럼 그래프처럼 학생들끼리의 표를 만들어 한명이 몇명까지 컨텍이 되는지 체크한다. 그리고 출력하면 된다.

어려워 보일수도 있으나 인풋만 집중하면 된다.

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

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

이건 그냥 딱봐도 초등부 문제다. 글만 요란하지 실상은 매우 쉽다. 이프 포문만 할수있다면 가볍게 풀 수있는 문제이다.

남자 여자 따로 분리해서 처리해주면 끝인 그런문제이다.

설명은 더이상 생략한다.

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

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

문제만 봐서는 이 문제는 어려울줄 알았는데...정말 쉬운문제였다. 쓸 내용도 없다. 그냥 시키는대로 코딩하면 끝난다.

단, 문제를 잘 보면 출력을 20개단위로 라인을 구분하라고 하였다. 이부분만 처리해주면 된다. 

이런건 사실 15분내에 풀어야 한다고 생각한다.

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

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

이 문제는 풀이를 어떻게 할지 생각을 하였다. 그런데 인풋의 최대가 1000이고 학년은 최대 5이므로 완전 탐색으로 해도 O(5*1000*1000)이니 O(5000000) 이 되므로 충분히 가능하다는 결론을 얻어 완전탐색으로 하였다. 분명 더 효율적인 알고리즘도 존재할것인데, 이 문제는 그렇지 않아도 될거같아서 이렇게 풀었다.

다른 방법으로는 그래프적으로 생각하면 좀 더 편할것 같기도 하다.

나는 먼저 학년별로 A학생과 나머지 학생들의 반을 비교하여 같은 반이면 반을 확인하는 배열을 만들어 계산하도록 하였다. 
역시 이방법도 위험할수있지만, 최대 인풋이 1000이므로 1000x1000을 하여도 충분하였다.

그리고 최대값이 같을경우 가장 작은 번호만 출력하라고 하였으므로 뒤에서부터 검색하여 앞녀석이 나오게 하였다.

역시 그렇게 어렵지 않은 문제였다.