문제분석

문제

이 문제는 트리에 대한 지식이 필요하다. AVL 트리는 균형 높이 성질에 따라 트리의 균형을 맞추는 문제이다. 그래서 문제의 설명처럼 왼쪽 부트리와 오른쪽 부트리의 높이차이가 1이하로 되도록 해야 하는 것이다.

가장 오른쪽 트리는 AVL 트리를 만족하지 않고 두개의 트리는 AVL트리를 만족하는 형태이다. 최대 V개로 최대 높이를 출력하기 위해서는 어떻게 해야할까?

바로 최소 V개가 주어질 때 트리의 높이를 바꾸는 기준점을 찾아주는 것이다.

입력과 출력!

입력과 출력 설명을 먼저 보자. 테스트 케이스의 개수가 주어지고 정점의 개수가 주어지면 입력될 때마다 최대 높이를 계속 출력한다.

예제

예제를 보면 헷갈릴 수도 있고 명확해 질 수도 있다. 일단 설명해보자면 먼저 5개의 테스트 케이스 주어진다.

그리고
1일 경우에 1
2일 경우에 2
5일 경우에 3
10일 경우에 4
1000000000의 경우에 42
라는 결과가 나와야 하는 것이다.

코드 분석

문제의 규칙

코드 분석을 들어가기 전에 먼저 문제의 규칙을 이해하는 것이 필요하다. 여기서는 트리의 형태가 주어지는 것이 아니다. 몇개의 정점이면 최대 높이가 얼마인지만 출력을 해주면 된다. 일단 3까지의 값은 어렵지 않게 트리를 그릴 수 있을 것이다.

1 -> 1
2 -> 2
3 -> 2
이렇게 나오게 된다.

이후에는 정점이 너무 많아지기 때문에 기준점을 기준으로 보게 되면
4 -> 3
7 -> 4
12 -> 5
이렇게 나온다.

그림 그리다보면 어느정도 느낌이 올것이다. 그럼 이제 규칙을 생성해보자. 나름의 규칙을 가지고 나온다.

일단 0일 경우에 0이라는 값을 설정해주고
1은 1로 설정한다.
2부터는 규칙이 있다.

2 = 0+1+1
4 = 1+2+1
7 = 2+4+1
12 = 4+7+1

규칙이 보인다.

기준점(n)보다 n-1, n-2에 있는 위치의 값, 그리고 +1을 해주면 n의 위치에 있는 값이 나온다.

초기 설정

graph=[0,1]
while True:
        if v<=1:
            break

이 규칙에 따라 초기 설정을 해보자.
문제의 규칙처럼 0과 1은 리스트에서 초기 설정을 해주었다. 그리고 만약 그 값이 나오면 별도 계산 없이 그대로 출력하기 위해 break를 걸었다.

break 규칙

while True:
        if v<=1:
            break
        else:
            
            num=graph[s]+graph[s+1]+1
            if num>v:
                break
            graph.append(num)
            if graph[s+2]>=v:
                break
            s+=1

앞에서 설명한 부분이 포함되어 있지만 하나의 반복문이라 포함시켰다.

2부터는 그대로 계산을 넣어주어야 한다. 이 부분은 else문에 넣어주었다. num으로 계산을 해주는데 만약 입력한 값(v)보다 크면 안되기 때문에 break를 걸었고 아니라면 리스트에 계속 추가해준다. 여기서 v와 같더라도 탈출하도록 한다. 탈출을 못했다면 다시 돌면서 다음 기준점을 찾아준다.

최종 코드

t=int(input())
for i in range(t):
    v=int(input())
    s=0
    graph=[0,1]
    while True:
        if v<=1:
            break
        else:
            
            num=graph[s]+graph[s+1]+1
            if num>v:
                break
            graph.append(num)
            if graph[s+2]>=v:
                break
            s+=1
    print(len(graph)-1)

코드를 총 정리해보자.
t로 테스트 케이스 받고 케이스 수만큼 돌리면서 v를 입력받는다. s는 계산을 위한 인덱스이다. while문은 break 규칙에서 언급했으므로 생략한다.

최종 결과를 출력하기 위해 고민을 했는데 s가 목표로 한 인덱스와 다르다는 점에서 기준점 리스트인 graph의 총 길이(0을 제외한) 값이 출력 값이 되었다.

결론

규칙과 이를 위한 식만 구하면 어렵지 않은데 이 규칙을 찾는게 굉장히 어려운 것 같다. AVL 트리를 그리면서 체크할 때 다르게 그린 부분도 많아 굉장히 헷갈렸다. 다른 사람의 그림을 보고 나서야 그림을 그릴 수 있었고 규칙에서도 계차수열(?)인줄 알았다가 다른 부분이 있어 그 규칙을 그리는데 어려웠다.

이 부분만 설계해서 그리면 어렵지 않은 것 같다.