22968-균형(swift풀이)

https://www.acmicpc.net/problem/22968

문제를 해석하는게 어려웠다. 그래서 나와같은 어려움이 있는 사람들을 위해 정리하자면..

정점의 개수가 주어질때 해당 정점으로 만들수 있는 AVL Tree의 최대 높이를 구하자는 것이다. AVL Tree = 왼쪽과 오른쪽 노드의 층 차이가 1층보다 크면 안됨. 결국 같은 층이거나 1층차이이여만 한다. 맨 오른쪽의 예제를 보면 1과 10이 2층차이난다. 그냥 이렇게 해석하면 끝!

딱 보자마자 아 이거 규칙이 있겟구나 생각을 하며 점을 찍어보았다.

1로 그래프를 찍었을때 딱 저 부분이 킥이다. 저 1이 생기는 순간 한층을 더 아래로 내릴 수 있다. 왜냐? 1층차이니까!! 완전이진트리가 될 필요가 없다.

그러므로 조금 더 규칙을 구하기 위해 경우를 좀 나열해보자.

점이 6개가 되는 순간 7개부터는 한층 더 설계공사를 하여 4층이 된다.  마찬가지로 12일때는 5층이 된다.

결국 1층일때는 1개가 필요하고

2층일때는 2개

3층일때는 4개

4층일때는 7개 

5층일때는 12개가 필요하다.

어? 3층일때의 4 = 1(1층일때) + 2(2층일때) + 1, 4층일때의 7개 = 4(3층) + 2(2층) + 1, 5층일때의 12개 = 7(4층)+4(3층) + 1

찾았다. 

이제 코드를 보면서 더 알아보자

//
//  22968.swift
//  Alogrithm2
//
//  Created by Sunho on 12/26/24.
//

import Foundation
let t = Int(readLine()!)!
var dp = Array(repeating: 0, count: 43)
dp[1] = 1
dp[2] = 2
for i in 3...42 {
    dp[i] = dp[i-1] + dp[i-2] + 1
}



for i in 0..<t{
    let v = Int(readLine()!)!
    var temp = 0
    for h in 1...42 {
        if dp[h] > v {
            break
        }
        temp = h
    }
    print(temp)
}

예제를 보면 최대값이 들어왔을때의 층은 42층이라고 이미 주고 있다. 그래서 각 층마다 최소의 개수를 구한 뒤

이후에 v값이 하나씩들어온다. 주의해야할것이!! v값은 노드의 개수로 층 수가 아니다. 헷갈리면 안댐.

그래서 7개 전에는 3층이고 15개 전인 14개까지는 4층이다. 하나씩 층별로 보며 주어진 것보다 층이 크다면 break걸고 이전의 값을 출력한다. 

최대 42번까지밖에 안돌기때문에 처리속도가 매우빨라 모두 구해줄 수 잇었다 끝!