[editorial] RUN Programming Contest - A. S@iNT그룹 권회장의 스타크래프트 대회

  • Taeyoon_Lee
    Taeyoon_Lee

    안녕하세요.
    S@iNT그룹 권회장의 스타크래프트 대회 문제 출제자입니다.
    출제 과정과 해설, 그리고 뒷이야기 등을 써보겠습니다.
    우선 처음 출제하게 된 배경은 개인적인 호기심 'ㅁ' 이었습니다.
    만약에 두 사람의 실력차를 "A가 B를 55% 확률로 이긴다."라고 가정하면,
    과연 몇 판 정도 경기를 해봐야 더 잘하는 쪽이 무난하게(?) 우승할까요?
    아무래도 A가 B보다 실력이 더 뛰어나니 많은 경기를 한다면
    전체 경기의 55% 정도를 이기겠지만, 실제로 세상에 거의 모든 대회는
    대체로 5경기, 많아야 7경기 내에 승부를 가리죠.
    이런 경우에 과연 운이 얼마나 작용할지 생각해보셨나요''?
    그 비밀(?)을 파헤쳐 보고자 문제를 만들었습니다''!
    그럼 이제 해법을 알아보죠.
    해법은 고등학교 수학 시간으로 돌아가면 나옵니다.
    확률과 통계(?) 시간에 배우지 않았나 싶네요.
    5경기를 한다고 가정하면, 3가지 경우가 있습니다.
    3경기만에 승리하는 경우, 4경기만에 승리하는 경우, 5경기만에 승리하는 경우
    각각의 경우를 살펴보면
    OOO (3경기만에 끝)
    XOOO (4경기..)
    OXOO
    OOXO
    XXOOO (5..)
    XOXOO
    XOOXO
    OXXOO
    OXOXO
    OOXXO
    이 모든 경우에 대해서 확률을 계산해서 더해주면 되는데요,
    A가 B를 이길 확률이 P라고 하면, 3경기만에 끝나는 경우를 P^3 으로 계산할 수 있습니다.
    4경기만에 끝나는 경우에는 P^3 * (1-P) 로 계산할 수 있을 테고,
    5경기만에 끝나면 P^3 * (1-P)^2 로 계산할 수 있겠죠.
    그래서 최종 답은 P^3 + 3 * { P^3 * (1-P) } + 6 * { P^3 * (1-P)^2 } 이 되는데요.
    여기서 곱해지는 상수 3, 6 등은 조합을 이용해서 구할 수 있습니다. (C라고 쓰고, 컴비네이션이라고 읽죠..)
    마지막 경기는 항상 이기니까 마지막 경기를 빼면, 상수값은 m개의 칸에 k개의 X를 그리는 경우의 수가 되겠죠.
    3경기만에 끝나는 경우에는 2개의 칸에 0개의 X를 그리는 경우의 수. 2C0 = 1
    4경기만에 끝나는 경우에는 3개의 칸에 1개의 X를 그리는 경우의 수. 3C1 = 3
    5경기만에 끝나는 경우에는 4개의 칸에 2개의 X를 그리는 경우의 수. 4C2 = 6
    그래서 최종적으로.. 아래와 같은 코드를 작성하시면 됩니다.

    #include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); ++i)
double p,q,c[101][101];
int k;
int main()
{
    c[0][0]=1;
    REP(i,100) REP(j,i+1) {
        c[i+1][j]+=c[i][j];
        c[i+1][j+1]+=c[i][j];
    }
    int tn;
    cin>>tn;
    while (tn--) {
        cin>>p>>k;
        p/=100;
        q=1-p;
        double pos=0;
        REP(i,k) 
            pos+=c[i+k-1][i]*pow(q,i);
        pos*=pow(p,k);
        printf("%.0lfn",(double)(pos*100.0));
    }
    return 0;
}

    계산을 해보면 이길 확률이 50%가 넘으면 더 많은 경기를 할수록 우승할 확률이 높아지고,
    50%가 안되면 더 많은 경기를 할수록 우승할 확률이 낮아지는 것을 볼 수 있습니다. 'ㅁ'
    그러므로 실력이 확실히 우위라고 생각하면, 긴 승부(?)를 하는 편이 좋겠죠?
    역시 단기전은 모르는 거니까요 ㅋㅋ
    79개의 답안 중에 36개가 맞아서 50%가 약간 안되는 성공률을 보였고,
    가장 빠른 Yes는 3분만에 구종만님이 받으셨네요.
    처음부터 A번으로 내려고 만든 문제였는데, 그 역할을 충실히 한 것 같아 기쁩니다.(?)
    전체 문제 수를 5개나 6개로 맞추려고 하다보니,
    A+B나 A*K+B 같은 허무한 문제로 하나를 낭비하고 싶진 않더라구요..
    이 정도로 끝내고.. 그럼 또 다음 에디토리얼을 기대해주세요 'ㅁ'

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    15년 전
10개의 댓글이 있습니다.
  • Being
    Being

    흑흑.. fastest를 놓쳤다능...


    15년 전 link
  • JongMan
    JongMan

    그후 177분 동안.............................


    15년 전 link
  • 세인트
    세인트

    감사합니다


    15년 전 link
  • astein
    astein

    빨간색 이쁘다능..


    15년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    여기 코드 깨졌어요...


    14년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    코드가 첨부된 에디토리얼은 대부분 코드가 깨졌네요..


    14년 전 link
  • JongMan
    JongMan

    태윤 쓰는 브라우저가 뭔가? 'ㅅ' 내가 집에 리눅스밖에 안써서 크롬에서밖에 테스트 안했더니 IE 에서 깨지는걸 몰랐네.. -_-;;

    오늘 저녁에 건드려보겠음 ㅎ


    14년 전 link
  • 일루
    일루

    크롬 깨져영.
    a rel="nofollow" href="/search?Search=%23include&Mode=like">#include

    이런식으로 나옴. 왼쪽 부등호 하나 뺐어여.


    14년 전 link
  • JongMan
    JongMan

    으윽 그르네영. 이거 포럼 내에서 #hashtag 식으로 트위터스러운 글 태깅을 지원해가지고... code 태그 안에선 끌수있도록 패치했었는데 프로덕션에 올리는걸 까먹었네여. 오늘밤에 고쳐보겠어여.


    14년 전 link
  • JongMan
    JongMan

    우우 위에거는 해결. IE 에서 렌더링 깨지는건 윈도우 머신이 있는 회사에서 해보겠어요. 'ㅅ'/


    14년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.