런타임 에러는 차치하고 일단 말씀하신 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] 입니다.
1325번 - 효율적인 해킹
감사합니다. 같은 문제에 빠져있었습니다. 처음 접근부터 이건 dp인가보네 ? 하고 시작했는데 이런 오류가 있었네요.
댓글을 작성하려면 로그인해야 합니다.
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번 컴퓨터를 탐색할 필요 없이 바로 해킹되는 컴퓨터 값을 알 수 있더라구요.
근데 이 방식으로 구현하니 계속 런타임 에러가 뜨네요.
혹시 논리 상에 오류가 있는 건가요?