[algospot] [NUMB3RS] 두니발 박사의 탈옥

두니발 박사^[각주:1]가 탈옥을 했는데,

하루가 지나면 한 마을에서 다른 마을로 옮겨간다.

이때 내가 있던 마을에서 갈 마을이 여러 곳이면 그곳으로 각각 갈 확률이 n등분된다.

이때 d일이 지났을 때 각 장소에 박사가 있을 확률을 구하여라... 하는 문제이다.

일단은 확률이니까 경우의 수를 전체 경우의 수로 나눈다든가 하는 생각이 들 수도 있지만,

잘 생각을 해보면 d일째의 각 확률을 알고 있으면,

모든 모서리마다(모든 시작점과 끝점에 대해서)

(d+1)일째에 끝점에 있을 확률 += 

d일째에 시작점에 있을 확률 x (1 / (시작점에서 갈 수 있는 모서리의 수))

이 됨을 쉽게 알 수 있다.

모든 모서리에 대해서 이 작업을 d번 하면 되므로 시간복잡도는 O(dE)인데,

문제에서 이미 인접행렬을 주기 때문에, O(dV²)으로 풀 수 있겠다.

이 글에서 하고 싶은 말은,

이 문제는 어느 날짜의 확률을 가지고 그 다음 날짜의 확률을 구하는 문제로,

전형적인 다이나믹 문제라고 볼 수 있다.

인접행렬을 adj[][]라고 하면

for(i=0;i<n;i++){

for(j=0;j<n;j++){

if(adj[i][j]){

dyn[to][j] += dyn[from][i] / degree[i];

}

}

}

뭐 이런 식으로 표현할 수 있겠다.

그런데 우리는 바로 전날의 확률만 알면 되므로, 이틀 전, 3일 전의 행방(?)은 전혀 몰라도 된다.

그렇다면 배열을 딱 2개만 쓰면 되지 않을까?

바로 이것이다.

dyn[0]과 dyn[1]을 이용해서,

dyn[0]에 0일째(교도소가 있는 마을에 박사가 있을 확률이 1, 나머지는 다 0)를 대입한 후,

dyn[0]을 이용해서 dyn[1]을 구하고(1일째의 확률은 dyn[1]에)

dyn[1]을 이용해서 dyn[0]을 구하고(2일째의 확률은 dyn[0]에)

dyn[0]을 이용해서 dyn[1]을 구하고(3일째의 확률은 dyn[1]에)

...

이렇게 구현하면 되겠다.

라고 생각하고 그대로 풀면 확률이 이상하게 커질 것이다.

바로 위의 코드에서 확률에 += 연산을 이용해서 그냥 더하는데,

예를 들어 3일째의 확률을 구하기 위해서 dyn[1]에다가 값을 더할때,

dyn[1]에는 1일째의 확률이 그대로 들어있으므로 이를 매번 초기화해주는 작업이 필요할 것이다.

n제한 50, d제한 100이기 때문에 dn²=250000 이라서 문제가 너무 쉽게 풀리는 것 같다.

n제한 10만,모서리 갯수 제한 10만, d제한 250 정도로 하면,

위에서 인접행렬 대신 모든 모서리를 이용하는 방식으로 바꿀 수 있겠지.

(여기서 모서리를 복잡하게 저장하지 말고 그냥 시작점 끝점만 기록해놓는 게 훨씬 간단하겠지?)

그러면 O(dE) 풀이가 나오고 시간 안에 풀릴 듯 하다.

1. 1) 두니발은 '한니발'의 패러디인 것 같다. 하나, 둘, ... [본문으로]