티스토리 뷰
난이도
문제보기
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 |
879A : Borya's Diagnosis (0) | 2017.10.27 |
codeground : 다트게임 (0) | 2017.10.08 |
868B : Race Against Time (0) | 2017.10.08 |
- Total
- Today
- Yesterday
- 아레나 시뮬레이션
- 데이터 중심 애플리케이션 설계
- 로젠
- paul wilton
- 시뮬레이션
- Propositional and Predicate Logic
- 이산수학
- 최단경로 알고리즘
- 명제논리
- 자바스크립트 예제
- 조합 코딩
- 이산 수학
- Trie
- arena simulation
- Arena
- 대규모 시스템 설계 기초
- 엄청난 인내심과 시뮬레이션을 위한 아레나 툴
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- 자바스크립트
- flutter
- 아레나시뮬레이션
- javascript
- rosen
- grafana cloud
- 아레나
- Discrete Mathematics
- beginning javascript
- Simulation
- 그라파나
- 백준
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |