<Algorithm> 105. 1057번 토너먼트

1. 1057번 토너먼트

• 문제해결능력을 묻는 문제

• 처음에는 반씩 나누면 될 것 같아서 분할 정복으로 접근을 했는데 테스트 하던 도중에 다음라운드에서 짝수 홀수가 바뀐다는 것을 알고 잘못 접근했다는 사실을 깨달았다..

• 다른 블로그에서 번호 메기는 부분으로 접근하면 된다는 힌트를 얻어서 간단하게 풀 수 있었다.

• 무조건 알고리즘으로 접근 할께 아니라 규칙을 찾는 것도 중요한 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int temp = a;
        a = Math.min(a, b);
        b = Math.max(temp, b);
        /******************************
         * 나누기 2 + 나머지 2의 식을 이용하면
         * 다음번 번호부여를 알 수 있고
         * 이 번호가 같을때까지 반복한다.
         *******************************/
        int count = 0;
        while(a!=b) {
            a = a/2+a%2;
            b = b/2+b%2;
            count ++;
        }
        System.out.println(count);
        
        /*int start = 1;
        int end = n;
        int total = 0;
        
        if(n%2 != 0) total++;
        
        while(n > 1) {
            n = n/2;
            total++;
        }
        if(a==end || b==end) {
            System.out.println(total);
            return;
        }
        
        while(start <= end) {
            
            int m = (start+end)/2;
            
            if(a >= start && a <= m && b > m && b <= end) {
                break;
            }else {
                if(a >= start && a <= m && b >= start && b <= m) {
                    end = m;
                }else {
                    start = m+1;
                }
            }
            total--;
        }
        System.out.println(total);
*/    }
}
 

참고 & 출처  

http://blog.naver.com/PostView.nhn?blogId=occidere&logNo=220875831899