알고리즘 설계 실습 - 삼각분할

---

문제

정N각형 P는 P의 두 꼭지점 쌍들을 연결하는 선분 (모든 선분은 교차하지 않아야 함)으로 N-2개 의 삼각형으로 분할될 수 있습니다. 예를 들어, 정사각형은 두 개의 삼각형으로, 정오각형은 세 개의 삼각형으로, 정육각형은 네 개의 삼각형으로 분할될 수 있습니다. 이러한 삼각형들의 집합 T 를 P의 삼각 분할이라고 합니다.

P의 삼각 분할의 집합 T 내의 두 삼각형 a와 b 사이의 거리는 a에서 b로 이동할 때 인접한 두 삼각형의 경계를 넘는 횟수로 정의됩니다. 이동하는 동안 언제든지 정N각형 P 내부에 머물러야 하며, P의 경계를 넘어서는 이동은 허용되지 않습니다. 우리는 정N각형의 삼각 분할 집합 T 내 모든 삼각형 쌍 사이의 거리의 최댓값 중에서 최소인 값을 찾는 프로그램을 작성해야 합니다.

예를 들어, 그림 1과 같이 삼각 분할을 진행하면, 모든 삼각형 쌍 사이의 거리 중 최대값은 A와 D사이의 거리이며, A와 D사이의 거리는 삼각형의 경계를 세 번 넘어야 하므로 3입니다. 하지만 그림 2와 같이 삼각 분할을 진행하면, 모든 삼각형 쌍 사이의 거리 중 최대값은 A와 D사이의 거 리 또는 A와 C사이의 거리이며, A와 D사이의 거리는 삼각형의 경계를 두 번 넘어야 하므로 2입 니다. 따라서 정육각형의 삼각 분할 T 내 모든 삼각형 쌍 사이의 거리의 최댓값 중에서 최솟값은 2입니다.

 

입력

첫째 줄에 정N각형의 변의 개수 N (3 ≤ N ≤ 1,000,000)이 주어집니다.

 

출력

첫째 줄에 정N각형의 삼각 분할 집합 T 내 모든 삼각형 쌍 사이의 거리의 최댓값 중에서 최소인 값을 출력하세요.

 

입력 예시 1

3

출력 예시 1

0

 

입력 예시 2

4

출력 예시 2

1

 

입력 예시 3

6

출력 예시 3

2

---

풀이

div_tri.py

n=int(input())

answer = 0
while n>2:
    if n==3:
        print (answer)
        break
    elif n==4:
        print (answer + 1)
        break
    else:
        answer += 2
        if n%2 == 1:    
            n = (n//2)+1
        else:
            n = n//2

아마 문제에서는 DP풀이법을 유도한거 같은데 규칙성을 찾아서 점화식 풀이처럼 if문으로 전부 풀었다. 정N각형 도형에서 인접한 3점을 이용하여 삼각형을 만들고 제거하면 n//2 또는 n//2+1 각형으로 바뀌고 사이드의 삼각형때문에 통과 거리가 양쪽에서 1씩증가해 2가 늘어난다. 이점을 이용하여 else문 내부의 조건문을 정해줬다. 그리고 삼각형이나 사각형인 경우 더 이상 따질 필요없이 정답을 구할 수 있기 때문에 삼각형일땐 그대로 사각형일땐 사각형 내부에 선하나가 그어지므로 1을 더해서 정답을 출력했다.

 

추가적으로 이러한 똑같은 원리로 DP로 풀어본다면 아래와 같이 풀 수 있겠다.

# Initialize DP array
DP = [0] * 1001

def main():
    k = int(input("Enter the value of k: "))

    DP[3] = 0
    DP[4] = 1

    for N in range(5, k + 1):
        tmp = N
        if tmp == 3:
            break
        elif tmp == 4:
            DP[N] += 1
            break
        if tmp % 2 == 1:
            DP[N] = 2 + DP[tmp // 2 + 1] + DP[N]
        else:
            DP[N] = 2 + DP[tmp // 2] + DP[N]

    print(DP[k])

if __name__ == "__main__":
    main()

---