글 읽기 - 백트래킹으로 푼 코드의 틀린 점을 알고 싶습니다.

qse1346 2년 전 0

안녕하세요.

문제를 처음에는 조합과 이항계수를 이용해서 풀고,

확률과 백트래킹으로도 풀 수 있을 것 같아서 코딩 후 제출했는데 채점 84%에서 막혀 질문 드립니다.

pa, pb가 각각 a와 b가 골 넣을 확률,

c[현재 라운드(총 18라운드)][골 넣은 개수]로 하여

1 - (a와 b가 모두 소수가 아닌 골을 넣을 확률)로 계산하여 풀어봤는데 코드의 문제점이 있을까요??

답변 주시면 감사하겠습니다.

#include <bits/stdc++.h>

using namespace std;

double pa, pb;

double c[20][20];

bool isPrime(int n){
    if(n <=1) return false;
    if(n == 2)  return true;
    if(n % 2 == 0)  return false;
    int sqrtn = int(sqrt(n));
    for(int div = 3; div <= sqrtn ; div += 2)
        if (n % div == 0) return false;
    return true;
}

void go(int idx, int cur_goal, double p, double init_p){
    if(idx == 0)    p *= 1/p;
    if(idx == 18){
        if(!isPrime(cur_goal)){
            c[18][cur_goal] += p;
        }
        else{
            return;
        }
    }
    else{
        go(idx + 1, cur_goal + 1, p * init_p, init_p);
        go(idx + 1, cur_goal, p * (1 - init_p), init_p);
    }
}

int main(){
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>pa>>pb;
    pa*=0.01;
    pb*=0.01;

    for (int i = 0; i < 20; ++i) {
        for (int j = 0; j < 20; ++j) {
            c[i][j] = 0;
        }
    }
    go(0, 0, pa, pa);
    double result_a = 0;
    for (int i = 0; i <= 18; ++i) {
        result_a += c[18][i];
    }

    for (int i = 0; i < 20; ++i) {
        for (int j = 0; j < 20; ++j) {
            c[i][j] = 0;
        }
    }
    double result_b = 0;
    go(0, 0, pb, pb);
    for (int i = 0; i <= 18; ++i) {
        result_b += c[18][i];
    }

    cout<<1 - (result_a * result_b);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

백트래킹으로 푼 코드의 틀린 점을 알고 싶습니다.

qse1346 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말