수직선 위에 서 있는 사람의 초기 위치가 숫자 N으로 주어지고, 왼쪽으로 이동할 확률이 L이라고 가정해 봅시다. 이때 점 N에서 출발하여 정확히 N번 이동한 후, 수직선상의 각 지점에 도달할 확률을 모두 구하는 것이 이 문제의 목표입니다. 매 이동은 왼쪽 또는 오른쪽으로 한 칸씩 이루어집니다.
예를 들어 입력이 n = 2, l = 0.5라면 출력은 [0.25, 0, 0.5, 0, 0.25]가 됩니다.
해결 접근 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 이동 횟수별로 각 위치에 도달할 확률을 누적해 나가는 방식입니다. 구체적인 단계는 다음과 같습니다.
high := 1 - low (오른쪽으로 이동할 확률 계산)
크기가 (n+1) x (2n+1)인 배열 A를 정의하고 모든 값을 0으로 초기화
A[1, n + 1] = high, A[1, n - 1] = low (첫 번째 이동 결과 설정)
i := 2부터 i <= n까지 반복하며 다음을 수행 −
j := 1부터 j <= 2 * n까지 반복 −
A[i, j] := A[i, j] + (A[i - 1, j - 1] * high)
j := 2 * n - 1부터 j >= 0까지 역순으로 반복 −
A[i, j] := A[i, j] + (A[i - 1, j + 1] * low)
마지막으로 i := 0부터 2*n+1까지 반복하며 A[n, i] 값을 출력
예제
다음 구현을 통해 더 자세히 이해해 보겠습니다 −
#include <bits/stdc++.h>
using namespace std;
void find_prob(int n, double low) {
double high = 1 - low;
double A[n + 1][2 * n + 1] = {{0}};
A[1][n + 1] = high;
A[1][n - 1] = low;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= 2 * n; j++)
A[i][j] += (A[i - 1][j - 1] * high);
for (int j = 2 * n - 1; j >= 0; j--)
A[i][j] += (A[i - 1][j + 1] * low);
}
for (int i = 0; i < 2*n+1; i++)
cout << A[n][i] << endl;
}
int main() {
int n = 2;
double low = 0.6;
find_prob(n, low);
}입력
2, 0.6
출력
0.36 0 0.48 0 0.16
출력 결과를 살펴보면, 0.36은 두 번의 이동이 모두 오른쪽(0.6 × 0.6)으로 이루어졌을 때의 확률, 0.48은 왼쪽과 오른쪽으로 각각 한 번씩 이동(0.6 × 0.4 × 2)했을 때의 확률, 0.16은 두 번의 이동이 모두 왼쪽(0.4 × 0.4)으로 이루어졌을 때의 확률을 의미합니다. 이처럼 동적 계획법을 사용하면 각 단계의 확률을 누적 계산하여 최종적으로 모든 지점에 도달할 확률을 정확하게 구할 수 있습니다.