알고리즘/백준 BAEK JOON
1057.토너먼트
IMyoungho
2020. 5. 1. 16:50
(*)이번에 풀어볼 문제는 백준의 1057 토너먼트이다. 시뮬레이션 분류파트에 있는 문제이다.
1057번: 토너먼트
김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음
www.acmicpc.net
시뮬레이션은 겉보기엔 쉬워보일 수 있고 이렇게 구현하면 되겠지라는 생각이 들지만
막상 구현을 해보라고하면 굉장히 헷갈리거나 손을 못대는 경우가 많다.
이번 문제를 푸는 키워드는 규칙성을 찾아내면 간단하게 풀 수 있다.
8명이 토너먼트에 참가했다고 가정하고 우리가 찾아야할 참가자 번호가 3, 5 라고 해보자.
이 때 3과 5의 변화를 알아보면 아래와 같다.
행방을 살펴보면 3은 3 => 2 => 1로 순서가 변화되고 5는 5 => 3 => 2로 순서가 변화된다.
이 변화에서 규칙성을 수식을 확인해보면 x = x/2 + x%2가 된다. 그러므로 그냥 while문을 돌려주면 된다.
< Code 설명 >
#include <iostream>
using namespace std;
int main() {
int n, a, b;
cin >> n >> a >> b;
int cnt = 0;
while (a!=b){ // 아래 수식대로면 최종적으로 둘이 같아짐
a = a / 2 + a % 2;
b = b / 2 + b % 2;
cnt++;
}
cout << cnt << "\n";
return 0;
}반응형