Red Salmon

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/%5BWA%5D1287.cpp

솔직히 이문제는 좀 너무했다.

먼저 사칙연산을 하려면 후외연산을 활용하는게 좋다. 이게 기본 자료구조이다. 

열심히 코딩을 했는데 자꾸 오답이나와서 생각해보니 입력의 최대가 1000자이다. 

즉, 9999999999999999999999999+1이 될 수도 있다.

int를 벗어나게 되니 당연히 빅인테져를 사용해야 하는데 자바가 아닌이상 C와 C++은 이마저도 구현해야한다.

그런데 또 사칙연산 전부가 들어간다. 즉 더하기 빼기 곱하기 나누기 전부 빅인테져 기반으로 구현해야 한다.

후위연산자체도 코딩하기 길고 짜증나는데 또 여기서 저런것 마저 요구하고 있다..그래서 나는 포기했다.

그럴만한 가치가 느껴지지 않았다.

물론 큰 시험이라면 당장 구현해야겠지만 그런 큰 시험이 아니므로 그냥 재껴두련다...

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1613.cpp

정말 쉬운 문제인데 참 오래 해맸다. 내가 왜 해맸는지도 모르겠다. 

플루이드 알고리즘을 사용할때 입력에서 1부터했으므로 당연히 1부터 검색을 해야하는데

습관적으로 0부터해서 계속 틀렸다 ㅠㅠ

이런 실수가 없어야 하는데 참 아쉽다.

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

정답 :  https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1298.cpp

이 문제는 그냥 이분매칭 알고리즘을 적용하면 풀리는 문제이다.

볼것도 없다. 최대 매칭을 구하라고하니 당연한 것이다. 알고리즘 역시 많이 썼던 그대로 하면된다.

그런데 항상 생각하는데, 쓰면 다 알고 보면 다 아는데 처음부터시작하면 오랜만에 하다보니 잘 기억이 나지 않고, 알고리즘이 쉽게 써지지 않는다. 더 많은 노력이 필요하다고 생각된다. 

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/9466.cpp

이 문제는 단순히 사이클을 찾고 끝내는 문제라고 생각했다. 그러나 학생이 무려 10만명이기 때문에 이중포문만 돌려도 TL을 피할 수 없다.

그래서 한번에 하는 방법을 생각해봤는데 O(n)은 사실상 불가능하고 내생각엔 O(2n)정도가 최대일것 같다. 

방법은 다음과 같다.

1번학생부터 n번학생까지 포문을 돌리되 1번학생과 연관된 모든 학생을 체크하면서 지워나간다. 이때 써클이 되는지 안되는지는 번호를 부여함으로써 알 수 있다. 써클이 되면 사용된 학생을 다시 돌아오게되고 이때 이 학생 직전에 몇번을 부여했는지를 파악하면 된다. 써클이 되지 않는 경우는 존재하지 않는다. 반드시 어디선가는 끝나야하기 때문이다. 

위와 같은 방법을 사용하면 빠르게 끝낼 수 있다.