[cpp 알고리즘] 백준 14613 너의 티어는? c++

문제 풀이

손으로 풀어볼 때 처음에 2000점에서 시작하여

1번 게임을 하고 나면 1950점이 될 확률 1*WinRate, 2050점이 될 확률 1*LoseRate, 2000점이 될 확률 1*DRate로 생각을 했다.

2번 게임을 하고 나면 최소 점수 1900, 최대 점수 2050 사이에서 점수를 얻게 될 것이고, 1번 게임을 하고 난 1950점이 될 확률에 이길 확률, 비길 확률, 질 확률을 곱한 만큼의 확률로 +-50점의 점수들을 얻는다. 이런 방식으로 생각해서 코드를 짜게 됐다. 

 

현재 점수가 2000점이고, 50point단위로 20번 점수를 더하거나 뺀다면 최소 점수는 1000점, 최대 점수는 3000점이다. 그리고 매번 50점 차이다. 이를 이용하여 배열을 만들었다.

1000~1499 → [0]~

1500~1999 → [10]~

2000~ → [20]~

2500~ → [30]~

3000~ → [40]

 

그리고 전 결과에서 다음 경기에 각각 이길 확률, 질 확률, 비길 확률을 저장하는 배열을 만들었다. 그래서 dp[점수][N번째 결과] = 그 점수를 받을 확률 이런 식으로 저장을 했다. 이게 DP를 쓴건가…(아닌 것 같기도) 뭐 쨋던 모든 경우를 다 구해서 마지막 dp[점수][20번째]의 값들을 비교하며 출력했다.

또 하나 생긴 문제는 처음에는 long double 형식의 ld bronze, silver, gold, platinum, dia; 을 사용하여 dp의 값들을 저장하였다. 근데 overflowr관련한 문제인 것 같게도 비정상적인 숫자가 출력하여 이를 배열에 저장하여 출력하였다. 배열도 long double을 사용하는데, 왜 배열은 되고, 변수 선언은 안 되는지 모르겠다.

 

코드

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

ld W,L,D;
ld dp[41][21];
ld ans[5];

int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> W >> L >> D;
    
    dp[20][0]=1;
    for(int i=0; i<20; i++){
        for(int j=0; j<41; j++){
            if(dp[j][i]!=0){ //값이 있으면
                //cout <<  i << " " << j << " ";
                cout << fixed; cout.precision(15);
                //cout << dp[j][i] << "\\n";
                dp[j-1][i+1]+=dp[j][i]*L;
                dp[j+1][i+1]+=dp[j][i]*W;
                dp[j][i+1]+=dp[j][i]*D;
//                if(dp[j-1][i+1] > 1 || dp[j-1][i+1] <0){
//                    cout << "overflow\\n";
//                }
//                else if(dp[j+1][i+1] >1  || dp[j+1][i+1]<0){
//                    cout << "overflow\\n";
//                }
            }
        }
       
    }
    
    //cout << "ss" << dp[19][40] << "\\n";
    ld bronze, silver, gold, platinum, dia;
    for(int i=0; i<41; i++){
        // cout << i << " " << dp[i][20] << "\\n";
        if(i<10) ans[0] += dp[i][20];
        else if(i<20) ans[1] += dp[i][20];
        else if(i<30) ans[2] += dp[i][20];
        else if(i<40) ans[3] += dp[i][20];
        else ans[4] += dp[i][20];
    }
    //cout << fixed; cout.precision(15);
    cout << fixed; cout.precision(8);
    for(int i=0; i<5; i++) cout << ans[i] <<"\\n";
    return 0;
}

 

알고리즘 분류

#수학 #다이나믹 프로그래밍 #브루트포스 알고리즘 #확률론