[백준] 1057번 토너먼트 JAVA (자바) 풀이

문제 1057 (수학, 브루트포스)

토너먼트 과정

•  1번부터 N번의 선수 중 서로 인접한 번호끼리 스타를 한다
• 이긴 사람은 다음 라운드에 진출하고 최후의 한 명이 남을 때까지 진행
• 라운드의 참가자가 홀수명일 경우, 마지막 번호는 다음 라운드로 자동 진출
• 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다 (처음 정해진 순서 유지하면서)

김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정

김지민과 임한수가 몇 라운드에서 대결하는지 출력해라

 

 

 [입력]

 

 :  첫째 줄에 참가자 수 N, 김지민과 임한수의 번호 입력 ( 2 ≤ N ≤ 100,000 자연수 )

 

 

 

 [출력]

 :  김지민과 임한수가 대결하는 라운드 번호 출력 (서로 대결하지 않을 때, -1을 출력)

 

 

 

 

 [참고]

 

https://velog.io/@yeoj1n/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1057%EB%B2%88-%ED%86%A0%EB%84%88%EB%A8%BC%ED%8A%B8

 

 

규칙찾기

 

1. 홀수일 경우 다음 라운드 순번 N/2 + 1 
2. 짝수일 경우 다음 라운드 순번 N/2
   
   
3. 두 공식을 합치면 N/2 + N%2 (짝수면 나머지 0, 홀수면 나머지 1)

 

 

 [코드]

 

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int jimin = Integer.parseInt(st.nextToken());
        int hansu = Integer.parseInt(st.nextToken());
        int round = 0;
        
        while(jimin != hansu){
            jimin = jimin/2+jimin%2;
            hansu = hansu/2+hansu%2;
            round++;
        }
        
        System.out.println(round);
    } 
}

 

 

 [해설]
     

 :  int N = Integer.parseInt(st.nextToken());  참가자수

    int jimin = Integer.parseInt(st.nextToken());  지민이 최초 순번
    int hansu = Integer.parseInt(st.nextToken());  한수 최초 순번
    int round = 0;  라운드 
        
 :  while(jimin != hansu){  지민과 한수 순번이 같다는 것은 같은 라운드라는 뜻
            jimin = jimin/2+jimin%2;  지민이 다음 라운드 순번
            hansu = hansu/2+hansu%2;  한수 다음 라운드 순번
            round++;  라운드 카운트
    }
        
 :  System.out.println(round);
    

 [시간 복잡도]

 

로그(log) 개념

log⁡₂​(N) = "2를 몇 번 곱해야 N이 될까?

 

해당 문제는 N을 계속 2로 나누는 상황

N에서 시작해서 2로 몇 번 나눌 수 있는지 계산하는 것 = log⁡₂​(N)번 나누기

 

얼핏 보면 O(N/2)라고 생각할 수 있지만, 이는 반복 횟수가 N에 비례하여 선형적으로 증가하는 경우에 해당하며 각 단계에서 크기가 지수적으로 감소하기 때문에 O(log⁡₂​(N)) = O(logN) 로 표현하는 것이 맞다

 

 

 

이제 풀어보러 갈께요 :)

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

https://www.acmicpc.net/problem/1057

 

1057번: 토너먼트