백준 Triangulation

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

 

삼각형은 하나의 삼각형만 있으니 지름이 0, 사각형은 삼각형에 삼각형이 하나 더 붙으니 지름이 1이다.

항상 지름을 이루는 한쪽 끝에는 두 변을 포함하는 사각형이 있으며 이 사각형이 전체 도형을 두 부분으로 분할한다.

따라서 분할되는 두 부분의 크기가 비슷할수록 지름이 작아짐을 보일 수 있고 재귀함수로 빠르게 답을 구할 수 있다.

 

 

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

int sol(int n){
    if (n == 1) return 0;
    else if (!n) return -1;
    return sol((n - 1) / 2) + 2;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    cout << sol(n - 2) << '\n';
}