Red Salmon

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

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

정말 생각을 많이 했던 문제이다. 우선 N이 1000자리라고 한다. 엄청나게 큰수이므로 문자열로 받아야 한다.

그런데 이건 이진수다. 뭔가 규칙이 반드시 있다는 말이다.

17N은 16N+N이다. 그리고 16N은 이진수로 뒤에 0000붙인것과 같다. 즉 인풋으로 들어오는 값에 0000을 붙이고 원래의 인풋을 더해주면 끝이난다.

계산이 매우 간단해지며 이진수 덧셈만 구하면 끝나는 문제이다. 

방법만 생각하면 금방 풀 수 있는 문제이다.

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

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

얼핏보면 굉장히 어려운 문제 같다. 하지만 잘 보면 어렵지 않다.

dp인듯하지만 아주 기초적인 부분만 물어보고있다.

문제의 요점은 큰녀석이 가장 밑에 깔리고 점점 더 작은 녀석이 위로 올라가는데, 여기서 포인트는 겹점을 허용하고 있다는 말이다. 

먼저 전체 인풋을 정렬을 시킨 후에 현재 사각형이 얼마나 위에 올라오는지 차곡차곡 저장시킨다. 그리고 모든 사각형에 대해서 계속 최대값을 갱신하는 식으로 하면 가장 큰 값을 저장시킬수있다. 

그리고 마지막에 자기 자신을 올려주는 식으로 진행하면 된다.

그렇게 어렵지 않은 문제이다. 왜냐면 이건 초등부 문제이기 때문이다.

출처 : 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자리의 숫자가 나온다면 풀 수 없다. 그때는 조금 다른 방법으로 접근해야할것이다. 키워드는 튜플이다.

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