Red Salmon

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

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

문제를 읽어보면 결국 하냐 안하냐 그차이이다. DP와 DFS사이에 고민을 했다. 둘다 방법이 있다. 그런데 이문제에서 주의깊게 봐야할것은 N이 20이다. 즉, DFS로도 충분히 풀 수있다는 것이다.

만약 N값이 30 이상이라면 사실상 DFS로는 가능성이 없으므로  DP로 접근해야한다. 

dp로 푼다면 각 사람별로 기쁨과 소모 체력을 누적시켜가며 최대값을 갱신하는 방식으로 진행해야겠다. 자세한 수식은 더 생각해봐야겠으나 해당문제에서는 DFS로 풀 수 있기 때문에  DFS로 풀었다. 그리고 단순히 선택을 하고 안하고의 차이이므로 전부 계산을 해보면 답이 나온다.

주의해야할점은 체력이 0이 되거나 마이너스가 되면 그어떠한 점수도 얻지 못한다는 점이다.

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

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

이제 이런문제는 보면 DP구나 하고 느낌이 온다. DP문제는 기본적으로 몇가지 틀이 있다. 이건 내가아는 틀중에 하나였다.

먼저 인풋을 보면 인풋이 200일때 엄청나게 긴 수가 나온다는 것을 알 수 있다. 즉, 문자열로 처리를 해야한다.

dp 는 무조건 처음 5~8개의 데이터는 직접 구해봐야한다.

이 문제의 경우 8일때 171인데 엄청나게 많은 경우의 수이므로 1~5까지 구하는 것을 목표로 삼고 모든 경우의 수를 구해봐야한다.

5까지 구해보면 다음과 같이 구성이 된다. 여기서 규칙을 찾아보면 되는데, 기본적으로 DP는 곱해보고 더해봐야한다.

그리고 보통 현재 데이터에서 최대 3개정도안에 규칙성을 가지고 있는데, 3번째 데이터를 기준으로 f(n-2)*2+f(n-1)이라는 규칙을 찾을 수있다. 물론 찾기까지 시간이 조금 걸렸다.

그외에는 이런식의 규칙이 이루어지고 있으므로 이를 구현하면 끝나는 문제이다.

https://www.acmicpc.net/problem/11727

똑같은 문제이며 그냥 10007로 나눠주면 끝나는 문제이다. 더 간단하다.

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

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

이건 뭐..C언어를 처음배울때 재귀 공부한다고 해봤던거다. 복습개념으로 다시 해봤다.

소스는 누구걸 봐도 똑같을거다. 이 방법이 제일 심플하고 거의 공식과 같이 사용되고 있기 때문이다.

from, by, to를 기본으로 to by, by from을 기억해두고 그 사이에 출력을 해놓으면 경로를 전부 알수있다.

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

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

문제가 시작부터 뭔가 복잡한 스멜이 난다. 결국 물을 여기저기 넣어두고 빼고 이걸 반복한다는 말인데...중복을 피하는것이 중요할것같다.

그리고 물이 최대 200L이다. 그럼 배열을 써서 간단히 할수있을것 같다.

그리고 물을 이동할때 모든 경우를 저장해놔야 중복을 피할수있을텐데, 맵을 쓰면 좋겠다.

그러나 A, B, C인데 3개의 인자를 전부 저장하면서 중복을 피하려면 tuple이라는걸 쓰면 된다.

http://www.cplusplus.com/reference/tuple/tuple/?kw=tuple

이곳을 참조하면 튜플에 대해 이해할수있다.

구조체를 사용하고자 한다면 map을 사용할수없다. 왜냐면 map에게 구조체를 인자로 주면 컴파일단계에서 에러가 난다. 이게 내가 뭔가 놓치고 있는 것 같으나, 일단 스킵하고  tuple을 쓰면 해결이 된다. 인자가 2개일때는 pair를 쓰고 3개부터는 tuple을쓰면된다. 그러나 tuple역시 한계가 있는데 내가 아는 바로는 10개정도가 한계이다. 그런데 사실상 5개이상부터는 tuple이 아닌 다른 방법을 찾아보는게 더 좋겠다.

아무튼 튜플을 사용하여 특정 컵이 다 차거나 빌때까지 이동을 계속 해주면서 체크해주면 된다.

그리고 A값이 0일때만 C의 데이터를 저장해야한다. 모든 경우에 대해서 중복을 계속 체크해주면서 피하면 제시간내에 정답을 낼 수 있다.