C++로 한 번에 2칸 또는 3칸씩 이동해 목표 지점에 도달할 확률 구하기

문제 개요

사람 A가 시작 위치 X = 0에서 출발하여 걷습니다. 이때 한 번에 2칸 또는 3칸만 이동할 수 있으며, 정확히 X = num 지점에 도달할 확률을 구하는 것이 이 글의 목표입니다. 2칸 이동할 확률은 P, 3칸 이동할 확률은 1 - P입니다.

입력 예시 1

num = 5, p = 0.2

출력:

0.32

설명:

num = 5에 도달할 수 있는 방법은 두 가지입니다.
2+3 순서로 도달할 확률: 0.2 × 0.8 = 0.16
3+2 순서로 도달할 확률: 0.8 × 0.2 = 0.16
따라서 총 확률은 0.16 + 0.16 = 0.32입니다.

입력 예시 2

num = 2, p = 0.1

출력:

0.1

문제 해결 접근 방식

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 각 위치에 도달할 확률을 순차적으로 누적 계산하기 때문에, 모든 경로를 일일이 탐색하는 재귀 방식보다 훨씬 빠릅니다.

풀이 과정은 다음과 같습니다.

크기가 num+1인 확률 배열을 선언하고 초기값을 설정합니다. probab[0] = 1, probab[1] = 0, probab[2] = p, probab[3] = 1 - p
i를 4부터 num까지 반복하면서 값을 하나씩 증가시킵니다.
각 i에 대해 probab[i] = (p) * probab[i - 2] + (1 - p) * probab[i - 3] 점화식을 적용합니다.
최종적으로 probab[num] 값을 반환합니다.
결과를 화면에 출력합니다.

알고리즘

시작
Step 1 → 한 번에 2칸 또는 3칸씩 이동하여 특정 지점에 도달할 확률을 계산하는 함수 선언
    float probab(int num, float p)
        double probab[num + 1] 선언
            probab[0] = 1 설정
            probab[1] = 0 설정
            probab[2] = p 설정
            probab[3] = 1 - p 설정
            int i = 4부터 i <= num까지 ++i 반복
                probab[i] = (p) * probab[i - 2] + (1 - p) * probab[i - 3] 설정
            반복 종료
            return probab[num]
Step 2 → main() 함수에서
    int num = 2 선언
    float p = 0.1 선언
    probab(num, p) 호출
종료

C++ 코드 예제

#include <bits/stdc++.h>
using namespace std;
// 한 번에 2칸 또는 3칸씩 이동하여 특정 지점에 도달할 확률을 계산하는 함수
float probab(int num, float p){
    double probab[num + 1];
    probab[0] = 1;
    probab[1] = 0;
    probab[2] = p;
    probab[3] = 1 - p;
    for (int i = 4; i <= num; ++i)
        probab[i] = (p)*probab[i - 2] + (1 - p) * probab[i - 3];
    return probab[num];
}
int main(){
    int num = 2;
    float p = 0.1;
    cout<<"probability is : "<<probab(num, p);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

probability is : 0.1

마무리

이처럼 동적 계획법을 활용하면 각 위치에 도달할 확률을 순차적으로 누적 계산하여 원하는 지점의 확률을 효율적으로 구할 수 있습니다. 시간 복잡도와 공간 복잡도 모두 O(num)으로, 가능한 모든 경로 조합을 직접 나열하는 방식보다 성능 면에서 큰 이점을 가집니다. 이 접근 방식은 계단 오르기 문제 등 다양한 확률 기반 DP 문제에도 응용할 수 있습니다.