[BOJ][Python]12928번 풀이

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

12928번: 트리와 경로의 길이

def sol(n,c):# n = 남은 노드 갯수, c = 현재까지 만들어진 2짜리 단일경로 갯수, 노드 2개짜리 트리에서 시작(2짜리 단일경로라 0개)
    if n == 0 and c == s:#모든 노드를 다 붙였을 때 단일 경로 갯수가 주어진 s와 같을 때
        print(1)# 가능하다
        exit()#프로세스 종료
    if n == 0 or t[n][c] or c > s: #n이 0이거나 t[n][c]가 True거나, c가 s보다 클 때
        return#리턴
    t[n][c] = 1
    for i in range(1,n+1):#남은 노드가 0개가 될 때까지 반복
        sol(n-i, c+i*(i+1)//2)#남은 노드, 2짜리 단일경로 개수

n,s = map(int, input().split())
t = [[0 for _ in range(1200)] for _ in range(50)]
sol(n-2, 0)
print(0)

문득 클래스 10은 얼마나 어려운 문제들이 있는지 궁금해져서 티어 오름차순으로 정리해봤는데 제일 쉬운게 다이아3인가 그래서 좀 고민하다가 클래스 8로 내려와서 거기서 가장 티어가 낮은 문제를 가져와봤습니다(사실은 해당 다이아 3문제도 풀긴 했습니다만 아직 시간초과 나는 부분을 고치질 못해서 끙끙대는 중입니다). 사실 잘 모르겠더라구요. 트리니 그래프니 학부생 때는 들어만 본 말이기도 하고, 이제 겨우 bfs 풀어내던 사람이 트리를 제대로 알리도 없구요. 그래서 풀이를 좀 찾아봤는데 아무것도 모르는 사람이 바로 보고 이해하기엔 좀 어려웠습니다. 그래서 저는 직접 손으로 트리를 하나씩 그려보면서 가능한 경우와 불가능한 경우를 찾는 작업부터 했습니다. 설명이 잘 적용되는지를 보기 위해서는 직접 구한 예시들이 진짜로 맞아떨어지는지 확인하는 것만큼 확실한 것도 없거든요. 그래서 혼자서 8번 정도까지 구해보니 최대한도로 나올 수 있는 단일경로의 갯수는 (n-1)*(n-2)/2이고 최소한은 n-2가 나왔습니다. 그럼 s가 해당 범위 안에 있으면 해결되겠네... 라는 것은 안일한 생각이었습니다.

 

플래티넘도 별 거 아니네~ 하면서 범위 조건문 하나만 딸랑 들고 가서 장렬히 패배했습니다. 그래서 왜 그런가 다시 구해놨던 걸 다시 보다보니 n = 5에서 반례를 찾을 수 있었습니다. 노드의 갯수가 5인 경우 2짜리 단일 경로의 갯수가 5개가 되는 그래프는 절대 나오지 않더라구요. 아무리 다르게 그리고 별 짓을 해봐도 불가능했습니다(사실 다르게 그린다고 한들 기본이 되는 형태는 정해져 있기 때문에 의미없다 걸 깨달은 건 좀 더 뒤의 일입니다).

 

그래서 이번엔 수식을 세워야겠다는 생각을 했습니다. n은 3~50의 범위를 갖기 때문에 그 모든 경우를 다 직접 그려서 확인하는 것은 불가능한 일은 아니지만 스마트한 방법은 아니죠. 실수를 할 가능성도 높구요. 식을 세우려고 보니 어떤 노드에 달라붙느냐에 따라서 단일경로가 늘어나는 갯수에 차이가 있었습니다. 간단하게 n = 4에 대해서만 그려서 보겠습니다.

현재 노드의 갯수와, 몇 번째 노드에 붙게 되었는지에 따라서 식을 세울 수 있을 것 같다는 생각이 들지 않으시나요? 거기다 이전의 형태에서 추가가 되는 방식이니까 dp를 활용할 수 있겠네요. 그럼 한 번 dp를 짜봅시다. 배열의 범위는 행은 n의 최대를, 열은 나올 수 있는 단일경로의 최대를 써주면 될 것 같습니다(단일 경로는 49*48/2이니 1200이 약간 안되겠지만 그냥 1200으로 쓰겠습니다). 해당 배열은 추가할 수 있는 노드의 갯수와, 늘어난 단일 경로의 수를 각각 인덱스로 가집니다. (n-2,0)부터 시작하는 이유는 노드가 2개일 때 2짜리 단일경로는 0개 이기 때문입니다. 해당 경우를 맨 처음으로 잡고, 노드를 추가해나갑니다. sol안에서는 조건문과 재귀를 이용해서 간선의 갯수를 늘려갑니다. 조건문은 일단 넘어가고 반복문을 보면, i가 1일 때는 1개만 붙였다고 보시면 됩니다. 맨 아래의 노드에 1개만 붙인다면 단일경로의 갯수는 1개 늘어나겠죠. i가 2가 된다면 2개를 붙인게 되는 거죠. 그러면 단일 경로는 1+2개만큼 늘어날 겁니다. 해당 공식은 가우스 공식입니다(등차수열의 합). i가 n-2가 된다면 어떨까요? (n-2)*(n-1)/2로 맨 처음에 최댓값은 얼마입니다라고 했던 것과 동일하게 나오는 것을 볼 수 있습니다.

반복문을 거치면 이렇게 되겠네요. i가 2가 나오는 경우는 i=1 이었던 재귀 호출이 끝났을 때입니다. 편의상 n이 4인 경우만 했지만 저런 형태로 진행됩니다. 사실 지금 풀어도 되는 문제는 아니었던 것 같습니다. 혼자서 생각을 많이 하기는 했지만 아무것도 모르니까 그걸 코드로 옮길 수는 없더라구요. 트리 문제도 낮은 난이도부터 슬슬 풀어야 할 것 같네요.