[AC] 1811 알약

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

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

dp다. 문제 설명에 있는 h와 w는 중요하지 않다. 그냥 경우의수만 따지면 되는 것이다. 그리고 n이 30일때 엄청 큰수가 나왔지만 long long으로 커버가 되는 수이다. 즉 배열을 long long으로 만들어야 한다.

dp는 언제나 그렇지만 먼저 순차적으로 만들어 봐야한다. 예제를 표현하면 다음과 같다.

n	1	2	3	4	5	6
f(n)	1	2	5	14		132

이렇게 구성이 되는걸 알 수있으며 우리는 5를 구하는 수식을 찾고 그 수식으로 구한 값으로 6을 추론하여 132가 나온다면 정답을 찾은것이다.

먼저 배열의 순서를 가지고 수열을 만들어 보려고 했으나 어떠한 방법을 사용해도 나오지 않았다. 그러면 이제 배열을 통해 추론해봐야한다.

보통의  DP는 단순 수식이 아니라면 배열의 위치값을 가지고 답을 구하게 하는 경우가 대다수이다. 이문제도 똑같다. 이것저것 역시 노가다를 뛰다보면 다음과 같은 규칙성을 찾을 수 있다.

이 그림은 정답을 말하는것과 같다. 현재 인덱스에서 아래녀석과 오른쪽 녀석에 +1씩 더해준다. 그리고 그과정을 계속 되풀이하면 최종적으로 m번째 원소는 arr[m][m] 을통해서 구할 수 있다. 문제는 0이들어오기전까지 계속 입력을 받으므로 미리 30x30배열을 만들어 값을 다 저장시키고 그 해당값만 출력하게 하면 되는 것이다.

dp를 나도 잘 하지는 못하지만 결국은 결과값들을 가지고 수식을 만들어보고 수식에는 대체적으로 감산이없으며 만약 찾을수 없을 경우에는 위와같이 배열을 펼쳐서 생각하다보면 결국 뭔가 나온다는 것이다.

그리고 드는 생각인데... dp도 결국 많이 풀어보면 순자들의 패턴만 보고도 어느정도 유추할수있을것같다. 왜냐면 dp가 낼수있는 패턴은 거의 정해져있다는 느낌이 많이 든다.

나 역시 이정도로 많이 풀어보진 않았지만 더 풀어서 경지에 오르도록 해야겠다.