Red Salmon

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

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

이 문제는 후위표기식 문제로써 저번에 후위표기식 자료구조를 만들어봤기에 그걸 응용해서 풀었다.

어렵지는 않으나 코딩이 진짜 귀찮은 것이다. 그래서 나는 조금 만 변형을 해서 사용했다.

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

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

이 문제는 말 그대로 최소 스패닝 트리이다. 

뭐 없다. 그냥 풀면 된다. 이론에 입각하여 이론대로 크루스칼 알고리즘을 사용하면 답이나온다.

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

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

이 문제는 과거에 내가 틀렸던 문제이다. 그리고 최근에 다시풀어봤는데... 

우선 나의 생각은 이러했다.

1. 현재 채널이 100번이기 때문에 오직 +와 -만 사용하여 카운팅수를 구해본다.

2. 근사치를 이용한다. 즉 3 4 5 번이 고장났는데 45번을 눌러야한다면 근사치인 29번과 60번을 눌러 플러스 마이너스를 통해 구해본다.

3. 자리수변경의 경우를 고려해본다. 즉 999번을 누르고싶은데 9번이 고장났다면 자리수를 변경시켜 1000을 만들고 마이너스를 하면 간단한 문제이다.

위 3가지 경우를 전부 구해서 3개중 가장 적은 값을 출력하게 하면 답이나오겠다 생각했다.

그런데 문제를 가만보니 최대인풋이 50만이다. 즉 for문을 돌려 모든 수를 대입해봐도 시간내에 풀린다는 말이 될것이다.

그래서 포문을 돌려 금지된 수가 있는지 체크하고 없다면 플마를 대입해서 최소값을 구하게 했다. 그런데 예제의 마지막경우엔 50만을 넘어서는 입력을 해야만한다. 그래서 나는 100만까지 해보라고했다. 어차피 100만도 시간내에 충분하다. 그랬더니 간단히 정답이 나왔다.

역시 알고리즘문제는...생각을 어떻게 하느냐의 차이이다. 

아무리 좋은 기술과 지식을 가지고있어도 간단히 생각해서 간단히풀면 그게 더 좋은 알고리즘이라고 생각한다.

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

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

이 문제는 모든 정점을 연결했을 때 최소를 구하라는 것이다. 즉! 크루스칼 또는 프림알고리즘을 구현해라 라는것과 같다. 이것은 최소스패닝트리 문제이며 MST라고도 한다. 

해당 알고리즘에 대한 설명은 구글링을 하면 너무 자세히 나와있기 때문에 굳이 내가 적어야할 필요가 없는것 같다. 

문제 자체도 해당 알고리즘만 구현하면 되는 간단한 문제로써, 모르면 못풀고 알면 푸는 그런 것이다. 

나는 싸이클이 형성되는 간선 체크를 mfind라는 함수를 사용했는데 이게 느릴줄 알았는데 상당히 빠른 속도를 보인다. (자주써야겠다.)

문제 자체는 특별할 것이 없기 때문에 여기서 마친다.