-
백준_1057 토너먼트알고리즘/simulation 2020. 1. 29. 09:25
링크 https://www.acmicpc.net/problem/1057
1057번: 토너먼트
김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음
www.acmicpc.net
접근
경기 대진표를 그려본다
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 3 5 8 9 11 13 15
1 8 9 13
8 9
8번과 9번의 번호를 추척하면 규칙을 찾을 수 있다
8 -> 4 -> 2 -> 1
9 -> 5 -> 3 -> 2 -> 1
9 - 5 = 4 = 9/2
5 - 3 = 2 = 5/2
...
다음 라운드로 진출할때는 번호 - (번호/2) 번의 숫자가 붙는것을 알 수 있다
두 선수의 번호가 같아질때까지
a = a-(a/2)
b = b-(b/2)
round++
위 공식을 코드로 그대로 옮기면 된다
#include <iostream> using namespace std; int main(void){ int n, p1, p2, round; scanf("%d %d %d", &n, &p1, &p2); round = 0; while(p1!=p2){ p1 = p1-(p1/2); p2 = p2-(p2/2); round++; } printf("%d \n", round); }
'알고리즘 > simulation' 카테고리의 다른 글
15685_드래곤커브 (0) 2020.01.29 1094_막대기 (0) 2020.01.28