코딩스토리

www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 옛날부터 이문제 한번 풀어보고 싶었는데 골드 3에 dp라 뭔가 엄청 어려울 것 같아서 못풀었었다. 오늘 날잡고 어떻게든 한번 풀어보자 하고 풀어봤다. 처음 문제를 봤을때 재귀가 떠올랐다. 이런 문제의 경우 dfs라고 하는게 맞겠지만.. 분명 dp와 재귀를 통해 풀 수 있을것 같은데 이게 맞을까 싶어서, 해결법이 맞는지를 한참 고민했다. 아무리 봐도 다른 방법은 떠오르지 않아서 그냥 풀었는데 다행히 맞았다...