백준 알고리즘 - 1057번 : 토너먼트

백준 알고리즘 1057번 토너먼트 문제입니다.

(참고 - https://www.acmicpc.net/problem/1057 )

코드)

#include <stdio.h>

int main() {

int n, J, H, temp, cnt=0;

scanf("%d %d %d", &n, &J, &H);

if(J>H) { //항상 H가 J보다 크다고 가정!

temp = J;

J = H;

H = temp;

}

for(; n>0; n/2) {

cnt++;

if(((H-J) == 1) && ((((H+1)/2) - ((J+1)/2)) == 0))

break;

J = (J+1) / 2;

H = (H+1) / 2;

}

printf("%d\n", cnt);

return 0;

}

- J와 H변수는 각각 지민과 한수 라고 표현하겠습니다. 위 문제는 어떠한 '규칙'을 찾아내야 하는 문제입니다. 또한 문제를 간편화 하기 위해 H가 J보다 항상 크다는 가정을 if문을 통해 정리해주었습니다.

이제 H는 J보다 항상 큰 상태가 되며, for문안에서 규칙을 통해 언제 만날 수 있는지를 구해내야 합니다.

J와 H가 만나는 경우는, 

(J와 H의 위치가 1차이가 나고) + 

(J의 위치를 절반으로 나눈 값(현재보다 바로 한 단계 상위 위치)과 H의 위치를 절반으로 나눈 값(현재보다 바로 한 단계 상위 위치)이 같을 때)

이 두가지 조건이 맞은 경우 지민과 한수가 만났다고 가정 할 수 있습니다.

하나라도 조건이 맞지 않을 경우에는 아직 만나지 않은 상태라고 가정하여 계속 J와 H를 반으로 나누어주며 조건이 성립할 때까지 cnt(카운트)를 더해주면 됩니다.

J와 H에 각각 (J+1), (H+1)을 해준 이유는 J나 H가 홀수일 경우를 염두에 둔 것입니다.

이렇게 하여 cnt를 최종출력해주면 몇 번만에 만나게 되었는 지 알 수 있게 됩니다.

위 문제는 규칙을 찾지못하면 풀기 힘든 문제라고 생각됩니다.

+Java)

import java.util.Scanner;

public class algo1057 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int[] arr = new int[3];

for(int i=0; i<3; i++) {

arr[i] = sc.nextInt();

}

if(arr[1] >= arr[2]) {

int min;

min = arr[1];

arr[1] = arr[2];

arr[2] = min;

}

int cnt=0;

for(; arr[0]>0; arr[0] = arr[0]/2) {

cnt++;

if(((arr[2]- arr[1]) == 1) && (((arr[2]+1)/2 - (arr[1]+1)/2)) == 0)

break;

arr[1] = (arr[1]+1)/2;

arr[2] = (arr[2]+1)/2;

}

System.out.println(cnt);

sc.close();

}

}

아, 더하여. 추가적으로 보여드리고 싶은 점이 있어서 사진 하나 첨부하도록 하겠습니다.

물론, 자바코드를 급하게 작성하며 배열을 사용하였고, 라이브러리도 사용하였음은 참고로 알아두시기 바랍니다.