[백준 17977번] [동적 계획법] Triangulation

 

어려워 보일 수 있으나 도형적으로 센스를 발휘하면 쉽게 구할 수 있다.

 

위의 발문에서 제시한 것처럼 각 다각형은 여러개의 삼각형으로 찢어서 생각할 수 있다.

그러한 측면에서 바라본다면 각각의 도형은 작은 도형의 모임으로 생각할 수 있고, 이 측면에서 DP를 읽었으면 충분하다.

 

그러면 각각의 경우에 대해서 상황을 재분석하면 다음과 같다.

꼭짓점이 홀수인 경우에는 결과적으로 삼각형을 하나 띄고 생각해보면 삼각형 1개와 꼭짓점이 짝수인 도형의 합으로 생각할 수 있다.

꼭짓점이 짝수인 경우에는 결과적으로 삼각형을 하나 띄고 생각해보면 삼각형 1개와 꼭짓점이 홀수인 도형의 합으로 생각할 수 있다.

 

그런데, 꼭짓점이 짝수인 경우에는 삼각형의 가장 맞은편에 꼭짓점이 존재하고 이를 기반으로 도형은 대칭적으로 나눠지고 반대로 홀수인 경우에는 비대칭적으로 나누어진다.

 

즉, 이를 기반으로 하나의 큰 도형을 작은 도형들의 최댓값과의 연산으로 생각할 수 있게 된다.

이를 기반으로 수식적으로 연산한 결과는 다음과 같다.

 

If 짝수 =대칭

 

= ((짝수 - 1) // 2 + 1 )인 도형에서의 최댓값  + 2

 

If 홀수 = 비대칭

 

= ((홀수 - 1) // 2 + 1 )인 도형에서의 최댓값 + 2

 

따라서 위의 내용을 기반으로 코드를 작성하게 되면 다음과 같다.

def triangulation(n):
    """
    This function is calculate the triangulation value by recursion
    """

    # Base case

    if n == 3:
        return 0
    
    elif n == 4:
        return 1

    else:
        result = triangulation((n - 1) // 2 + 1) + 2
        save_result[n] = result
        return result

# Initial setting

n = int(input())

save_result = [0] * 1000001
save_result[3] = 0
save_result[4] = 1

# Print result

print(triangulation(n))

항상, 문제를 작은 문제로 구획해서 그것을 활용하여 연산을 해야할 경우에는 DP(Dynamic programming)을 고려하도록 하자.