끄적끄적

[문제] https://www.acmicpc.net/problem/1005 [처음 생각] 힌트가 위상정렬인걸 보고 일단 위상정렬을 찾아봤다... 찾아보니 위상정렬 알고리즘은 여러 일들에 순서가 정해져있을 때 순서에 맞게 나열할 때 사용하는 알고리즘이어서 이 문제처럼 건설 순서가 정해져있고 순환이 없는 그래프이므로 사용하기 적절한 듯 하다. 위상정렬 알고리즘을 그대로 사용하되 중간에 max 값 갱신해주는 부분만 넣어주면 되지 않을까?! [풀이] 위의 방법처럼 하려고 했는데 위상정렬을 짜려니 길어져서 혹여나 다른 방법으로 할 수 있을까 찾아보니 DP 재귀로 한 사람이 있었다. 위상정렬을 하면 나중에 의존관계를 고려해야 하는데 DP로 풀면 의존관계를 고려하지 않고 거꾸로 지어야 할 마지막 건물번호를 기준으로 ..