[백준] 알고리즘 분류(브루트포스 알고리즘,JAVA)1057번, 토너먼트

문제 링크

1057번: 토너먼트

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 참가자가 홀수명이면 마지막 번호 인원은 부전승으로 처리됩니다.

2. 김지민과 임한수는 만날 때까지 항상 승리합니다.

3. 김지민과 임한수가 만났을 때 라운드를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 김지민과 임한수의 번호를 감소시키면서 둘이 만나는 라운드를 탐색합니다.

 

3. 둘이 만났을 때 라운드를 결과로 출력합니다.

 

 

라운드 진행

 

진행되는 경기에 번호는

 

선수의 번호가 짝수일 때선수 번호 ÷ 2

 

선수의 번호가 홀수일 때

(선수 번호 + 1) ÷ 2

 

두 인원이 라운드에서  만나려면 경기의 번호가 같아야 합니다.

 

김지민 번호 ÷ 2 == 임한림 번호 ÷ 2

 

각 라운드에서는 절반의 인원이 떨어지게 됩니다.

 

승자는 다음 라운드의 번호는 아래의 점화식을 통해 정해집니다.

 

현재 번호가 홀수이고 승리하였을 때

 

(번호 + 1) ÷ 2

 

현재 번호가 짝수이고 승리하였을 때

 

번호 ÷ 2

 

예를 들어.

 

번호가 3번이고 승리하였을 때

 

다음 라운드 번호 : (3 + 1) ÷ 2 = 2번

 

번호가 4번이고 승리하였을 때

 

다음 라운드 번호 : 4 ÷ 2 = 2번

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N = 16

 

김지민 : 8번

 

임한수 : 9번

 

2. 김지민과 임한수의 번호를 감소시키면서 둘이 만나는 라운드를 탐색합니다.

1라운드

 

김지민과 임한수의 경기장 번호 확인

 

8(김지민) ÷ 2 != 10(임한수) ÷ 2

4 != 5

다음 라운드 진행!

 

김지민 번호 = 4

임한수 번호 = 6

2라운드

 

김지민과 임한수의 경기장 번호 확인

 

4(김지민) ÷ 2 != 6(임한수) ÷ 2

2 != 3

다음 라운드 진행!

 

김지민 번호 = 2

임한수 번호 = 4

 

3라운드

 

김지민과 임한수의 경기장 번호 확인

 

2(김지민) ÷ 2 != 4(임한수) ÷ 2

1 != 2

다음 라운드 진행!

 

김지민 번호 = 2

임한수 번호 = 2

 

4라운드

 

김지민과 임한수의 경기장 번호 확인

 

2(김지민) ÷ 2 != 2(임한수) ÷ 2

1 == 1

대결 성사!

 

3. 둘이 만났을 때 라운드를 결과로 출력합니다.

 

둘이 만나는 라운드 4을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 입력값을 띄어쓰기 기준 나누었습니다.
• 각 번호를 이용를 이용해서 라운드를 진행합니다.
• 대결이 성사되었을 때 라운드를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int kim = Integer.parseInt(st.nextToken());
        int lim = Integer.parseInt(st.nextToken());
        //김지민 번호 홀수 일 때 경기 번호를 위해서 + 1
        if(kim % 2 == 1)
            kim++;
        //임한수 번호 홀수 일 때 경기 번호를 위해서 + 1
        if(lim % 2 == 1)
            lim++;
        int round = 1;
        //라운드 진행 탐색
        while(true){
            if(kim/2 == lim/2)	//대결 성사!
                break;
            kim = win(kim);
            lim = win(lim);
            round++;	//라운드 증가
        }
        bw.write(round + "");	//대결 성사된 라운드 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //다음 라운드 번호 구하는 함수
    static int win(int n){
        int result;
        if(n%2 == 1)	//홀수 일 때
            result =  (n+1)/2;
        else		//짝수일 때
            result = n/2;

        if(result %2 == 1)
            return result+1;
        else
            return result;
    }
}