Red Salmon

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

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

그냥 참 쉽다. 이건 저번에 설명한 stable_sort만 알고있다면 거저먹기의 문제이다.

그걸 모른다면 구현해야 할테니 참으로 번거로울것이다. 기본적인 STL을 아는것 또한 실력이라고 생각한다.

물론 어떤 STL을 쓰든 한번쯤은 구현해봐야하며 내부 구조에 대한 이해정도는 해 놓은 상태에서 사용해야한다.

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

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

난 항상 이런 뒤집는 문제를 좋아하지 않는다. 경험상 뒤집으라는 문제는 생각도 뒤집어야 한다.

나는 이문제에 어떠한 규칙이 있지 않을까 하며 엄청 찾았다. 

몇몇의 규칙을 찾았지만 그 규칙을 전부 적용시키려면 소스가 너무 길어진다.

그러나 늘 말하지만 소스가 길다면 알고리즘은 틀린것이다. 

대게 알고리즘 문제의 정답은 소스가 길지 않다는 점을 알아둬야한다.

그럼 다시 인풋을 보자. 최대가 8이다. 왠지 dfs나 bfs등의 재귀를 사용해도 충분할것 같다.

그리고 8이면.. 12345678인데 거꾸로해도 87654321이다. 약 9천만 정도의 경우의수를 가질 수 있다. 물론 이 전부를 사용하지는 않을 것이다. 아마도.. 그러나 배열의 크기를 얼마를 잡아줘야할지 감이 오지 않으므로 STL의 힘을 빌린다.

그리고 bfs로 구간별로 조금씩 뒤집어본다. 계속 뒤집는다 언젠간 나올것이다. 생각해보면 엄청 뒤집지도 않는다. 왜냐면 불가능한 경우가 엄청 많다. 그리고 중복처리도 걸리게 되니 생각보다 많이 뒤집을수는 없다.

그러나 내풀이의 치명적 결함은 만약 인풋이 1~8까지 가아니라 8개의 숫자이지만 10 20 30 100 이런식으로 2자리의 숫자가 나온다면 풀 수 없다. 그때는 조금 다른 방법으로 접근해야할것이다. 키워드는 튜플이다.

수를 합쳤다가 나눴다가 다시 합쳤다가 나눴다가를 바놉ㄱ하지만 이게 큐를 사용하기에는 깔끔할것이기에 이 문제에는 적합한 방법이라고 볼 수 있다. 

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

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

칸을 이동하란다. BFS라고 말하고있는것과 같다.

다만 이동할수있는 범위가 생각보다 많다. 하나하나 다 해주라는 말이다. 참 귀찮게 하는 문제이다.

문제자체는 어렵지 않다. 

bfs몸풀기 문제로써 20분 컷으로 풀어보면 좋을것 같다.

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

정답 : 

문제를 보면 인풋이 천만개이다. 그리고 더 읽어보면 10,000보다 작거나 같은 자연수라고 한다. 즉, 10000개의 숫자들을 가지고 천만개를 입력하게 되니 반드시 중복이 있다는 말이다. 

이 부분을 캐치해야 문제를 풀 수있다. 나는 맵을 사용하여 풀었는데, 맵을 사용하지 않고도 풀 수있다.

맵을 사용하지 않는다면 어차피 숫자는 10000개니까 bool 함수를 써서 인풋이 들어오면 그 부분을 참으로 맞춘다.

그리고 int배열을 하나만들고 해당 부분을 카운팅해준다.

입력이 끝나면 for(1만) 을 돌려서 bool이 참이면 그에따른 int배열의 개수만큼 그 수를 출력해주면된다. 

결국 입력은 천만번이지만 정렬도 없고 그냥 포문 1만번으로 답을 구할수있다.

그리고 이런 문제의 경우 인풋도 출력도 엄청많은데 cin, cout보다는 scanf와 printf를 센스있게 써줘야한다. 

속도면에서 엄청난 차이가 있다.