heeguk95   5년 전

문제를 처음 풀 때 모든 노드에서 DFS로 접근하니 맞았습니다.

근데 생각해보니 예제에서 1번을 해킹하면 총 4대가 해킹되는데

1 - > 3 - > 4
           -> 5

이 과정을 DP 배열로 표현하면 DP[1] = 4, DP[3] = 3, DP[4] = 1, DP[5] = 1 로 표현 되므로 

1번 컴퓨터를 탐색하면 3, 4, 5번 컴퓨터를 탐색할 필요 없이 바로 해킹되는 컴퓨터 값을 알 수 있더라구요.

근데 이 방식으로 구현하니 계속 런타임 에러가 뜨네요.

혹시 논리 상에 오류가 있는 건가요?

win198978   5년 전

런타임 에러는 차치하고 일단 말씀하신 DP의 경우에는 다음과 같은 논리의 오류가 있어보입니다.

만약 1 - 2 - 3

            4 - 3

과 같은 관계라면 (1해킹하면 2, 4 해킹 가능 / 2해킹하면 3 해킹 가능 / 4해킹하면 3 해킹 가능)

dp[2] = 2, dp[4] = 2 이나, dp[1] != 1+dp[2]+dp[3] 입니다.

win198978   5년 전

아, 위에 오타가 있네요. 

dp[1] != 1+dp[2]+dp[4] 

입니다.

heeguk95   5년 전

감사합니다! 논리상의 오류를 드디어 알게됐네요!

cheese_null   4년 전

감사합니다. 같은 문제에 빠져있었습니다.  처음 접근부터 이건 dp인가보네 ? 하고 시작했는데 이런 오류가 있었네요. 

댓글을 작성하려면 로그인해야 합니다.