[22984 C++,python] 반짝반짝 2 / cout << fixed; cout.precision(10);

2022년 02월 16일 SUAPC Winter 대회 2번째 팀 연습이었다. 

1번째 팀연습때 0 솔의 부담감을 가지고 열심히 풀어보았지만 결과는 1 솔이었다. 

내가 풀었던 문제는 22984의 반짝반짝2 와 22986의 Flat Earth 2문제였는데 사실 아직도 Flat Earth 문제는 이해가 가지 않는다.

그래서 우선 22984번을 리뷰하려고 한다.

 

나는 수학을 좋아하기때문에 확률 구하기라는 문제의 콘셉트를 보고 바로 달려들었다. 

처음에 떠올랐던 풀이 방법은 주어진 전구의 확률을 배열의 홀수번째에 입력을 한 뒤에 한 개의 전구가 꺼질 확률과 켜질 확률을 일일이 다 세어주면서 총 몇 개의 전구가 켜지는 지를 cnt로 세준 다음에 더하는 방식이었다.

원래 고등학교에서 확률과 통계를 배울때 일반적으로 쓰는 방법이다.

 

그런데 이렇게 1번 전구가 켜졌을 때와 꺼졌을 때, 2번 전구가 켜졌을 때와 꺼졌을 때 하나하나씩 따지게 되면 

전구의 개수는 최대 100,000이므로 경우의 수는 2의 100,000승이 된다.  결국 틀린 풀이임을 확신했다. 

고등학교 때 수학을 풀 때도 습관적으로 쓰는 공식이나 풀이로 풀게 되면 더 빙빙 돌아가야 하는 문제들이 있었기에 

원초적인 방법으로 풀어야겠다는 생각이 강하게 들었다. 

이 문제에서 주어진 테스트케이스가 2개가 있었는데 

그중 하나는 홀수갯수였고 나머지 하나는 짝수 개수였다. 

그래서 나는 전구의 갯수가 홀수인지 짝수인지에 따라서 계산을 달리 하면 DP로 풀 수 있을 것 같다는 생각에 머리를 굴려봤다.

그렇지만 1분만에 깨달았다. 

'전구의 켜질 확률이 제각각이다'라는 문제 조건을 경시했다는 것을..

 

이렇게 2번의 잘못된 길을 들었다가 정신을 차려보니 

기댓값을 각각 구해서 더해주면 된다는 아이디어가 떠올랐다. 

 

천천히 설명을 하자면,

 

전구가 1개 있을때

1번 전구가 켜질 확률이 0.5일 때 

전구가 켜질 기댓값은 1 * 0.5이다.

 

전구가 2개 있을 때

1번 전구가 켜질 확률이 0.3이고 2번 전구가 켜질 확률이 0.4일 때

전구가 켜질 기댓값은 0.3 * 1 + 0.4 * 1 = 0.7이다. 

당연한 소리를 당연하지 않게 하는 이유는 바로 내가 습관적으로 풀었던 방법은 다음과 같았기 때문이다. 

전구가 켜질 기댓값 = (전구가 2개 켜질 확률)*2 + (전구가 1개 켜질 확률)* 1 * (전구가 1개 켜지는 경우의 수)

 

그래서 기댓값을 각 전구마다 하나씩 더해주는 방법으로 + 꼬마전구가 켜질 확률도 더해주는 방법으로 구하는 코드를 작성하였다.

이때 시간은 대회 시작 후 정확히 39분 후였다. 

#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define xx first
#define yy second
#define all(v) (v).begin(), (v).end()


int N;
double arr[100001];
double notexP(double N){
    return 1.0-N;
}


int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N;
    double ans = 0.0;
    for (int i=0; i<N; i++){
        cin >> arr[i];
        ans += arr[i];
    }
    
    for (int i=0; i<N-1; i++){
        ans += notexP(arr[i]) * arr[i+1] + notexP(arr[i+1])*arr[i];
    }
    cout << ans;


}

이렇게 제출하면 틀렸습니다. 가 나온다. 거의 4% 정도에서..

 

뭐가 틀렸지? 괜히 함수를 썼나? 하고 함수가 안 들어간 코드를 다시 제출했다. 

예외 케이스가 더 있나 라는 생각이 들었다. 혹시 몰라서 N이 1인 경우도 다시 작성해주었다. 

(대회 67분 후)

#include <iostream>
using namespace std;
int N;
double arr[100001];
int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N;
    cout << fixed; cout.precision(10);
    double ans = 0.0;
    for (int i=0; i<N; i++){
        cin >> arr[i];
        ans += arr[i];
    }
    
    if (N==1){
        cout << arr[0];
        return 0;
    }
    for (int i=0; i<N-1; i++){
        ans += (double)(1.0-arr[i])*arr[i+1]+(double)(1.0-arr[i+1])*arr[i];
    }
    cout << ans;


}

이렇게 제출했는데도 똑같은 결과 틀렸습니다가 나왔다. 

그래도 시간 초과가 아닌 틀렸습니다가 나와줘서 기뻤다. 

하지만 더 이상 찾아낼 예외 케이스는 없다고 생각해서 C++ 코드를 그대로 python으로 옮겨줬다.

사실 난 구현하는 부분에 있어서는 파이썬이 훨씬 편한데 요즘 들어 C++을 더 자주 쓰자!라는 생각이 들어 C++로 작성했던 것이었다.

 

그런데 웬걸 파이썬으로 다 작성했는데 백준 맞았습니다는 개뿔 VScode에서도 돌아가지않았다.

스스로에 대한 화남을 참아내고 구글링과 에러 메시지를 보고 코드를 뜯어고쳤다. ^^ 아직 내 수준이 이렇다. 

그리고 혹시 몰라 python 3 가 아닌 pypy로 제출해줬다. 

N = int(input())
lst = list()
ans = 0.00
lst = list(map(float,input().split()))
for i in range(N):
    ans += lst[i]

if N==1:
    print(ans)
else:
    for i in range(N-1):
        ans += (1.00-lst[i])*lst[i+1] + (1.00 - lst[i+1])*lst[i]
    print("{:.6f}".format(ans))

4%에서 틀렸습니다가 떴던 그 속도와 달리 아주 빠르게 풀이 진행률이 올라갔다.

다행히도 맞았습니다가 뜨게 되었고 우리 팀에서 첫 솔을 해냈다. 아주 뿌듯! 

 

어쨌거나 팀 연습에서의 내 성과는 이 상황에서 진척 없이 끝났고 집에 가서 내 C++ 코드가 어떤 점이 잘못된 것인가를 비교해봤다. 

다른 사람들의 코드가 가장 큰 차이점은 바로

cout << fixed; cout.precision(10);

 

이 한 줄이었다. (사실 2줄일지도)

소수점 이하의 자릿수를 10자리를 받고 10자리를 나타내 준다는 의미라고 한다. 

그래서 이 문제는 어쩌면 내게

cout << fixed; cout.precision(10);

 

를 알려주고 싶었던 것이 아닐까 생각했다.