ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 879B: Table Tennis
    알고리즘 문제/implementation 2017. 10. 27. 11:16

    난이도

    어려울뻔했는데 난이도는 3/10

    문제보기


    n 명의 사람들이 탁구를 치는데, 일렬로 서서 게임을 하게된다. 맨 처음엔 게임은 첫 사람과 둘째 사람이 하게되는데 이긴사람은 그대로있고 진 사람은 줄의 맨 뒤로 가게된다.

    어떤 사람이 k번째 이기면 게임은 종료되며, 이기고 진다는 판정은 입력받은 각 플레이어의 힘ai으로 결정된다.

    출력은 k번 승리한 플레이어의 힘을 출력하면 된다.

    2<=n<=500, 2<=k<=10^12,   1<=ai<=n

    즉, 아래와 같이 입력되면

    2 2

    1 2


    2명의 플레이어 중 2번 이긴사람의 힘을 출력하란거다.

    정답은 2이다.

    입력이

    4 2

    3 1 2 4

    인 경우 4명중 2번이긴 사람의 힘을 출력하면되니 3을 출력하면된다.

    2 1000000000000

    2  1

    인 경우 2를 출력하면된다.


    해당문제도 꽤 쉽다.

    하지마나 입력값이 어마어마하므로 몇가지 처리가필요하다. 언제까지고 k만큼이나 체크할 수 없다. 1연산수가 2억이넘으면 시간초과일것이 뻔하다. 해당 index의 파워가 최대와 같다면 걍 그녀석을 출력하면된다. 

    그외에 이기고 지는 것을 처리하는 그런건 배열을 전체적으로 앞당기고 할 필요도 없이 i, j index를 설정해 i를 전판에 이겼던 놈, j를 새로온놈처럼 취급해 각각 상황에 맞게 처리하면된다.


    즉 다음과 같은 경우를 생각해보자.

    4 2 

    2 1 3 4 

    다음과 같은 알고리즘(순서도)를 생각해보았다.

    cnt=k, i=0, j=1;

    while (cnt){ 

    2 1 3 4 ,     

    i  j       ... cnt--;

    2 1 3 4   

    i     j    .... i=j, j++,cnt= k-1;

    2 1 3 4  

          i j  .... i=j, j++, j>=n?, j=0, cnt=k-1;    

    2 1 3 4

    j       i ... cnt--;

    }

    print a[i];


    나는 알고리즘은 맞았으나, k를 입력받는걸 long long으로 받지 않았기 때문에 틀렸었다. (대회에서는 몇가지 테스트케이스만 맞으면 pretest 통과라고 해주기땜시... 몰랐음 ㅡ.ㅡ;;) 

    대회가 끝난 후 확인해보니 시간초과도 아니였고.... 입력 받은 자료형 때문이였단걸 확인 후 조금은 억울하기도했으나 내책임.... 푸하하 ㅠ.ㅠ


    소스보기

    https://github.com/ingyeoking13/algorithm/blob/master/cf/implementation/879B.c




    '알고리즘 문제 > implementation' 카테고리의 다른 글

    908B New Year and Buggy Bot  (0) 2017.12.30
    892B Wrath  (0) 2017.11.18
    879B: Table Tennis  (0) 2017.10.27
    879A : Borya's Diagnosis  (0) 2017.10.27
    codeground : 다트게임  (0) 2017.10.08
    868B : Race Against Time  (0) 2017.10.08

    댓글 0

Designed by Tistory.