백준 17977 - Triangulation

문제

 

www.acmicpc.net/problem/17977

17977번: Triangulation

 

 

풀이

 

각 정다각형에서 다음과 같은 답이 나온다.

 

 

1. 정육각형의 경우 내부에 정삼각형이 있어야 거리가 최소가 된다.

이때 최대거리는 (정삼각형의 최대 거리 +2) 가 된다.

 

2.정팔각형의 경우 내부에 정사각형이 있어야 거리가 최소가 된다.

이때 최대 거리는 (정사각형의 최대 거리 +2) 가 된다.

 

3. 정십각형의 경우 내부에 정오각형이 있어야 거리가 최소가 된다.

이때 최대 거리는 (정오각형의 최대 거리 +2) 가 된다.

 

이 성질을 이용해서 짝수 정다각형에서 다음과 같은 점화식을 만들 수 있다.

dp[n] = dp[n/2] + 2 (n은 짝수)

 

홀수 n다각형의 경우 n+1정다각형의 경우와 답이 같게 된다.

따라서 최종으로 다음 점화식을 만들 수 있다.

 

dp[n] = dp[(n+1)/2] + 1

 

 

코드

 

#include <bits/stdc++.h> 
using namespace std; 
 
int a[1000001];
 
int main() 
{ 
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
 
    int n;
 
    a[3] = 0;
    a[4] = 1;
 
    for (int i=5; i<=1000000; i++)
        a[i] = a[(i+1)/2] + 2;
    
    cin >> n;
    cout << a[n];
 
    return 0; 
}