[AC] 1005 ACM Craft

출처 : https://www.acmicpc.net/problem/1005

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.07/1005.cpp

이 문제는 참 그렇다. 이렇게 많이 틀린 문제가 있엇던가 싶다. 

그래도 이번엔 정답을 맞았다. 1년전에 도전했고 9개월전 6일전 1일전 도전하여 결국 풀어냈는데 생각해보면 이 단순한걸 왜틀렸을까? 왜생각을 못했을까 싶다..

위상정렬이라는것이 필요하다고 하여 공부해보았고 참 요긴하게 쓰이겠구나 했지만, 위상정렬이라는 개념을 모르더라도 DP와 dfs만 안다면 풀 수 있는 문제였다. 

결국은 최장길이를 구하는 문제인데 dfs로 전부 탐색해서 구했다.

풀이는 다음과 같다.

1. 인풋을 입력받지만 나는 벡터에 값을 담을때 반대로 담았다.

2. 찾고자하는 건물번호를 입력을 받으면 그 지점에서부터 시작을 하였다.

3. 그리고 dp[now] 에 값이 있다면 그값을 리턴하고 아니라면 dp[now]에 현재 arr[now]값을 주고 계산을 시작하였다.

그런데 여기서 계산을 한다.

4. 포문을 열고 현재 녀석과 연결된 녀석을 살펴보고 해당녀석을 다시 dfs로 작업을 시작한다.

그럼 결국 여기저기 찾으러 다닐텐데 만약 dp[now] 값이 존재하면 이미 만든 값이므로 그 값을 사용할테고 그값을 사용하면서+val이 크다면 그 구한값에 +val만하여 사용하고 아니면 그냥 쓰는식이다. 

간단한 문제라고 생각되는데 왜이리 해맸는지 모르겠다. 

가만보면 난 이런 dp+dfs에는 알면서 자주틀리는거같다. 나중에 다시풀어보거나 비슷한 문제를 다시 접해봐야겠다.