PS 일기 4월 5주차

중간고사 시험과목이 하나, 코딩테스트도 하나, 주말에 수업도 하나 + 발표 준비까지 낀 주차라 상당히 정신없는 5주차 PS 일기입니다.

 

1289 트리의 가중치

 

정확한 풀이에 대해 설명을 들었고, 예시 출력까지 잘 되었지만 WA를 받았습니다.

이는 입력을 받을 때 임의로 간선의 방향을 정해서 받았는데 일단 이 점이 문제라고 힌트를 받았습니다.

따라서 간선 입력을 양방향으로 받고 1번 정점을 시작으로 dfs를 돌려 각 정점의 자식 정점들을 모두 찾아주었습니다.

 

D(u) : 정점 u를 루트로 하는 서브트리에서 u를 끝으로 하는 경로의 가중치

위와 같이 dp 배열을 정의하고 아래와 같은 점화식을 세웠습니다.

$D(u) = \sum\limits_{1\leq i\leq k}  (D(v_{i} * W_{u,v_{i}}) + W_{u, v_{i}})$ (u의 자식 노드들이 v)

다만 위의 경우 정점 u를 포함하지만 끝으로 하지 않는 경로에 대해서는 커버하지 못합니다.(u에서 꺽이는 경로)

 

따라서 $F(v_{i})$를 정점 u의 임의의 자식 $v_{i}$라고 할때, u를 끝으로하고 $v_{i}$를 지나는 경로의 가중치라고 정의해줍니다.

이후에 이렇게 구한 각각의 $F(v_{i})$들의 곱을 구해주면 되는데 이는 $ab + ac + bc$ 이런 꼴이 됨을 알 수 있습니다.

$ab + ac + bc = ((a + b + c)^2 - a^2 - b^2 - c^2) /2$임으로 이를 이용하여 $O(N)$만에 값을 구해 줄 수 있습니다.

 

정점 u를 끝으로 하는 경로의 가중치와 정점 u를 포함하지만 끝으로 하지 않는 경로의 가중치를 모두 더해주면 문제에 대한 해답을 구해 줄 수 있겠지만 이를 구현하여 제출 시 WA를 받고 있습니다.

 

18858 훈련소 가는 날

논산인 경우는 2가지 케이스가 존재합니다.

a,b,c 순서로 숫자가 있을때

 

1) $a \geq b$ 인 경우

이 경우에 c 어떤 숫자가 와도 상관 없습니다.

 

2) $a < b \leq c$인 경우

a < b 인경우에는 c에 올 수 있는 숫자가 정해져 있습니다.

 

이렇게 구한 dp배열 두개를 1부터 M까지 전부 더해주면 답이여야하는데 WA를 받습니다.

아무래도 배열에 값을 잘못 구해준 것 같습니다.

 

7570 줄세우기

P[i] : 번호가 i인 어린이의 위치

이렇게 정의하고 dp(i) : 번호가 i인 어린이를 끝으로 하는 가장 긴 증가하는 부분 수열을 구해주면 됩니다.

배열 p의 정의로 반대로 이해해서 삽질을 오래 했습니다.

 

8983 사냥꾼

동물을 x축 기준으로 정렬시키고 가장 왼편에 있는 동물부터 시작하여 그 동물 바로 오른쪽에 있는 사대를 찾아주었습니다.

이때 찾아준 사대를 사대[j]라 하면, 사대[j]와 사대[j-1]에서 동물까지의 거리가 L보다 같거나 작으면 ans++

 

WA를 받는걸로 보아 어디서 미스가 난 것 같은데 다시 잘 찾아봐야 할 것 같습니다.