[cpp 알고리즘] 백준 22984 반짝반짝2

문제 풀이

1. 첫번째는 어떻게든 0과 1의 배열의 모든 경우의 수가 2^N만큼 있으면 이를 비교해서 문제를 풀 수 있을 거라 생각했는데 0과 1의 배열의 모든 경우의 수를 구할 때 O(2^N) 으로 시간초과가 발생한다. 이를 비교해서 문제를 푼다는 것은 불이 켜졌다는 의미인 1의 개수 + 연속되는 두 수가 00,01,10,11인 경우에 대해 추가 카운트를 더한 후에 이 때의 확률을 곱하면 된다고 생각했다.

 

2. 그래서 배열에 저장해서 값을 바로 이용하면 될 거라 생각했지만, 메모리가 2^N만큼 발생할 것이고, N의 최대 크기가 100000이기 때문에 메모리 초과가 발생할 것이라 생각했다.

 

3. 이에 dp를 사용해보자고 생각해서 dp[i][j]를 이용해 i번째 까지 전구에 대해서 끈 경우를 j=0, 켠 경우를 j=1로 생각했다. 이 때 dp[i][j]가 그 때까지의 기댓값을 나타내야 하지만, 어떻게 계산해야 하는지에 대해 고민이 많았다. 예를 들어 dp[2][0](2번 전구가 꺼지는 경우) = dp[1][0](1번 전구가 꺼지고)(1-p[2])(2번 전구가 꺼질 확률) + dp[1][1](1번 전구는 켜져있고)(1-p[2])(2번 전구가 꺼질 확률). dp[2][1] = dp[1][0]*p[2]+dp[1][1]*p[2]… 이런식으로 식을 작성해보려고 했는데 각각의 사건이 발생할 확률이랑 그 때의 전구 갯수를 어떻게 매번 구하는지… 해결이 안되었다. → 맞는 것 같긴한디….모르겠다… → 이 방법 다시 생각해보기

 

4. 진짜 1시간 반 정도 고민한 것 같은데,,,모르겠어서 출처를 보다 suapc길래 풀이를 찾아봤다.

✓ 불이 들어온 기존 전구 개수의 확률변수를 X, 불이 들어온 추가 전구 개수의 확률변수를 Y라고 할 때, 불이 들어온 전구 개수의 기댓값은 E(X + Y)로 표기할 수 있습니다.

✓ [기댓값의 선형성] Theorem : 임의의 확률변수 X, Y 에 대해서 **E(X + Y) = E(X) + E(Y)**를 만족한다. 위의 Theorem은 확률변수 X, Y 가 서로 독립이 아니어도 성립하기 때문에 E(X)와 E(Y)를 따로 계산하면 된다.

✓ i번째 전구가 불이 들어오는지에 대한 확률변수를 Xi로 정의할 때, E(Xi) = pi를 만족한다. (Xi=1 (i번째 전구가 켜진 경우), Xi=0 (i번째 전구가 꺼진 경우))

✓ i번째 전구와 i + 1번째 전구 사이에 있는 추가 전구를 i번째 추가 전구라고 할 때, i번째 추가 전구에 불이 들어오는지에 대한 확률변수를 Yi로 정의할 때, E(Yi) = pi(1-pi+1)+pi+1(1-pi)를 만족한다. (Yi=1 (i번째 추가 전구가 켜진 경우), Yi=0(i번째 전구가 꺼진 경우))

 

5. 근데,,,suapc 추가 해설 보니까 아래 처럼 나와 있어서 3번방법도…잘 해 봅시다…

 

dp(i, j)를 다음과 같이 정의하는 방법으로 O (N) dp로도 풀 수 있습니다.
– i번째 기존 전구까지만 고려했을 때, 불이 켜진 전구 개수의 기댓값.
– j 가 1인 경우는 i번째 기존 전구가 켜진 경우, 0은 i번째 기존 전구가 꺼진 경우를 의미한다.

회고

suapc 문제는 코드 길이보다는 수학적으로 얼마나 알고 있냐…의 문제같다…ㅎㅎ

아 그리고 문제에 출력한 값과 정답과의 절대 오차 또는 상대 오차가 10^-6이하여야 한다 고 했는데 딱히 조건일 거라 생각하지 않고 코드를 짰더니 4%에서 틀렸습니다 가 나왔다. cout << fixed; cout.precision(6); 이 코드를 꼭 넣어주어야 한다.

 

코드

#include <iostream>
#define ll long long
#define ld long double
using namespace std;

int N;
ld parr[100010];
ld ans=0;

int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N;
    
    for(int i=0; i<N; i++){
        cin >> parr[i];
        ans += parr[i];
    }
    
    for(int i=1; i<N; i++){ //사이의 전구가 켜질 확률
        ans += (parr[i-1]*(1-parr[i]) + (1-parr[i-1])*parr[i]);
    }
    cout << fixed; cout.precision(6);
    cout << ans;
    
    return 0;
}

 

알고리즘 분류

#확률론 #수학 #기댓값의 선형성