다이내믹프로그래밍1 [백준] 2637번: 장난감 조립 | Python 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 틀린 이유 1. 처음엔 dp[7]로 제출했다. (멍청...) 2. N개의 노드가 주어졌을 때, 기본 부품, 중간 부품을 거쳐 완제품이 되는 노드가 N번임을 가정하고 다이내믹 프로그래밍으로 풀었다. (dp[N]=1 에서 시작) 정답 코드 각 노드 간 선후관계를 생각해야 할 땐 위상 정렬을 사용한다. 위상 정렬된 topology[N-1]가 완제품 노드임을 이용해 다시 다이내믹 프로그래밍으로 풀었다. 완제품부터 기본부품까지 탑다운(?)으로 .. 2022. 12. 10. 이전 1 다음
