BOJ 13703 물벼룩의 생존 확률

수면 k센티미터 아래에 위치한 물벼룩이 1초마다 위 또는 아래로 1센티미터 이동하고 수면에 닿으면 물매암이에게 먹혀서 죽는다. n초후의 경우의 수는 2의 n제곱가지가 있을것인데, 그 중 생존할 경우의 수를 구하는 문제이다.

처음부터 생존할 경우의 수를 구하려는 것 보다 죽는 경우(수면에 도달하는 경우)의 수를 구해서 전체 경우의 수에서 빼는 것이 나아보인다.

좀 더 생각해보면 k<=n인데, 
k==n인 경우는 수면 k센티미터 아래에서 시작해서 n초뒤에 수면에 도달하려면 계속 위로 올라가야 한다. k==n인 경우는 수면에 도달하는 경우의 수는 1가지이다.
k<n인 경우는 어떨까? 일단 한 번 수면에 도달하면 그 이후로는 의미가 없다. 즉, 그 이후는 볼 필요가 없다. 그 이후는 2^(남은 시간) 의 경우의 수 일 것이다. 그리고 현재 위치보다 남은 시간이 더 작으면 수면에 도달할 수 없다.

음...dp로 접근해보면, d[pos][rsec] = 현재 위치 pos, 남은 시간 rsec일 때의 수면에 도달할 수 있는 경우의 수.(벼룩이 죽는 경우의 수)

한 번 구현해 봐야겠다.
오.. AC를 받았다. 다른 분들을 보니 나처럼 죽는 경우를 전체에서 뺀 경우도 있지만 바로 생존할 경우의 수를 구한 분들이 더 많아 보인다.

처음에는 dp로 생각하기 힘들었는데, 차근 차근 적고 정리해보다 보니 운좋게 생각이 떠오른 것 같다. 감사합니다.