15647번 - 로스팅하는 엠마도 바리스타입니다
아래와 같이 코드를 짰는데 기본적인 아이디어는
1. 1번 노드를 언제나 루트로 잡음.
2. size[n]배열에 각 노드마다 자식 노드+자기 자신의 총 개수를 넣음
3. 이후 sumdp[n] 배열에 각 자식 노드들이 자신의 부모 노드에 도달하기까지 최단거리 합을 저장해놓음
ex) 만약 입력이
3
1 2 3
2 3 7
이렇게 주어지면 1번 노드를 루트로 해서 size[0]에는 자식노드 개수 2+자기 자신으로 해서 size[0]=3, size[1]=2, size[2]=1;
이후 sumdp에는 3번 노드는 자식이 없으니 sumdp[2]=0, sumdp[1]=7, sumdp[0]=13이런 식으로 올라감
4. 위의 과정이 끝나면 사전 준비는 완료된 것이고 이제 진짜 dp 실행
5. for문으로 루트를 제외한 각 노드들을 방문하며 각 노드를 방문할 때마다 while문과 stack으로 자신의 부모를 타며 올라감
만약 끝까지 올라가서 루트까지 닿는다면 루트 직전 노드를 a라고 하자. 그럼
a의 전체 최단거리 합=sumdp[루트]+a와 루트 사이 거리*(루트를 포함한 a외부 트리에서 개수(a의 자식이 아니고 a 자신도 아닌 노드들 개수)-a 자신 사이즈)
이렇게 성립이 되고
dp[a]=a의 전체 최단거리 합-sumdp[a]
이렇게 dp를 저장하고 이후 다시 루트에서 stack을 pop하며 내려가면
특정 노드 n의 최단거리 합은 dp[n부모]+sumdp[n부모]+(부모와의 간선 거리)*(n의 외부트리 노드 개수-((n 자식 노드 개수)+1)(이것도 결국에는 n 자신 사이즈))
dp[n]은 n최단거리 합-sumdp[n]
이런 식으로 점화식을 만들어서 했는데 왜 안될까요.... 아니 50% 정도까지는 잘 갔는데 갑자기 틀렸습니다가 나와서 진짜 너무 슬픕니다. 제발 도와주세요
풀었습니다.... 그냥 int형을 long으로 고치니까 되네요...
여러분은 이런 실수하지 마세요ㅠ
거리의 합이 대략 d * N^2에 비례해서 int는 오버플로우가 나요
ㄲㅂ
댓글을 작성하려면 로그인해야 합니다.
06vfsunny 1년 전
아래와 같이 코드를 짰는데 기본적인 아이디어는
1. 1번 노드를 언제나 루트로 잡음.
2. size[n]배열에 각 노드마다 자식 노드+자기 자신의 총 개수를 넣음
3. 이후 sumdp[n] 배열에 각 자식 노드들이 자신의 부모 노드에 도달하기까지 최단거리 합을 저장해놓음
ex) 만약 입력이
3
1 2 3
2 3 7
이렇게 주어지면 1번 노드를 루트로 해서 size[0]에는 자식노드 개수 2+자기 자신으로 해서 size[0]=3, size[1]=2, size[2]=1;
이후 sumdp에는 3번 노드는 자식이 없으니 sumdp[2]=0, sumdp[1]=7, sumdp[0]=13이런 식으로 올라감
4. 위의 과정이 끝나면 사전 준비는 완료된 것이고 이제 진짜 dp 실행
5. for문으로 루트를 제외한 각 노드들을 방문하며 각 노드를 방문할 때마다 while문과 stack으로 자신의 부모를 타며 올라감
만약 끝까지 올라가서 루트까지 닿는다면 루트 직전 노드를 a라고 하자. 그럼
a의 전체 최단거리 합=sumdp[루트]+a와 루트 사이 거리*(루트를 포함한 a외부 트리에서 개수(a의 자식이 아니고 a 자신도 아닌 노드들 개수)-a 자신 사이즈)
이렇게 성립이 되고
dp[a]=a의 전체 최단거리 합-sumdp[a]
이렇게 dp를 저장하고 이후 다시 루트에서 stack을 pop하며 내려가면
특정 노드 n의 최단거리 합은 dp[n부모]+sumdp[n부모]+(부모와의 간선 거리)*(n의 외부트리 노드 개수-((n 자식 노드 개수)+1)(이것도 결국에는 n 자신 사이즈))
dp[n]은 n최단거리 합-sumdp[n]
이런 식으로 점화식을 만들어서 했는데 왜 안될까요.... 아니 50% 정도까지는 잘 갔는데 갑자기 틀렸습니다가 나와서 진짜 너무 슬픕니다. 제발 도와주세요