Level2 - 예상 대진표

레벨 2 부터는 단순 알고리즘이 아니라 문제를 어떻게 해결해야하는지 찾는데에 시간이 많이 걸리는거 같다.

 

대진표가 있다면 A랑 B랑 몇번째에 만날지 예측해주라는 문제

A = 1 

B = 2 

라면 1번째에 바로 만나는거라 1을 리턴

A = 1 

B = 4

라면 2번째에 만나는 거라 2를 리턴

A = 4

B = 5

라면 최종 3번째 니깐 3을 리턴

 

무조건 A와 B는 이긴다는 규칙이 있으니깐

 

이런식으로 이긴다면 계속 좁혀지는걸 확인

뭔가 DP를 사용해야 하나 하다가 그냥 DFS각이 보여서 DFS로 접근

 

(찾게 된 규칙)

+ 둘의 차이가 1이면 리턴 && A가 홀수이면 리턴 

 

A = 2 , B = 4 라면 , 위의 식이 만족이 안되니 다시 위로 승격, 그럼 2는 1이되고 4는 2가 되며 위의 조건이 만족하고 2를 리턴

A = 4 , B = 5 라면 위의 A는 홀수인 식이 만족이 안되, A = 2로 승격 B = 3으로 승격 여전히 A는 짝수, A = 1로 승격 B = 2로 승격 두 가지 조건이 만족이 되고 3을 리턴 

 

생각은 오래했는데 코드는 너무 쉬움...

 

public static  int solution(int n, int a, int b)
{
    if(a>b){ // a 가 크다면
        if(b%2==1 && Math.abs(b-a)==1) return 1;
        else return 1+solution(n, (int) Math.ceil(a/2.0), (int) Math.ceil(b/2.0));
    }else{ // a 가 작다면
        if(a%2==1 && Math.abs(b-a)==1) return 1;
        else return 1+solution(n, (int) Math.ceil(a/2.0), (int) Math.ceil(b/2.0));
    }
}

 

아니 풀이 리뷰에 한 줄로 끝낸 사람도 있던데... 그건 아직 이해를 못하겠다.