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/2526

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

예전에 풀었던 문제이다. 근데 재채첨으로 오답이나와서 다시풀어줬다.

결국 키워드는 p로 나눠주는데 이게 97이므로 어떤 수가 나와도 결국 97아래의 숫자끼리 중복이 일어난다는 말이다. 그리고 그 중 하나의 숫자라도 있으면 다시 반복이 된다는것이 키워드다.

그 처리만 해주면 되는 매우 쉬운 문제이다.

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

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

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

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

설명은 더이상 생략한다.

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

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

이 문제의 풀이는 이미 내가 과거에 풀어본 배열내 구간 계산이므로 세그먼트 트리를 적용시키면 된다. 설마 이 문제를 읽고 구간 a부터 b까지의 합을 계속 더하고 더하고 하는 사람은 없을것이다. 무조건 TL이 나올것이다.

세그먼트 트리도 정답이지만 이 문제는 조금 더 생각하면 다른 해법도 있다.

어차피 구간내의 합이기 때문에 0부터 계속 더해나가는 것이다. 즉

a[0]=a[0]

a[1]=a[1]+a[0]

a[2]=a[2]+[1]

a[3]=a[3]+a[2]

이렇게 하면 구간 0부터 n까지의 합이 계속 저장이 된다. 그리고 입력으로 구간이 입력이 되면 그 구간을 빼주면 된다.

즉 a~b구간의 합은 0~b구간의 합에서 0~a구간의 합을 뺀다면 a~b구간의 합이 되는것이다. 이렇게 푸는것도 간단히 푸는 방법이다.

그러나 나는 세그먼트트리 연습겸 저렇게 풀어봤다.

이런 문제가 참 괜찮은 문제라고 생각한다.