BOJ 문제풀이 (W27)

무려 2주만의 PS입니다!!

그간 코딩테스트와 중간고사가 겹쳐서 못하고 있었는데 시간 비면 짬짬이 해야겠습니다.

4학년 올라오니까 거의 매주 시험입니다 😭😭😭

 

16325 king's color

트리 dp 문제입니다.

간선이 주어지는데 문제 풀이와는 전혀 관계없습니다.

어떤 정점이든간에 2가지 경우만 생각해주면 됩니다.

어떤 정점 u를 색칠했을때, 그 색이 다른 정점을 칠할때도 사용되는 경우와 그렇지 않은 경우가 있습니다.

 

이때 F(i, j) 를 i개의 정점을 j개 이하의 색으로 칠하는 경우의 수라고 정의하면

후자의 경우 $K*F(N-1, K-1)$ 입니다.

정점 u를 칠하는 경우 k개, 나머지 정점들을 k-1개의 색으로 칠해주는 경우

전자의 경우 $(K-1)*F(N-1, K)$입니다.

정점 u를 부모와 다른 색으로 칠해주는 k-1가지 경우, 나머지 정점들을 k개의 색으로 칠해주는 경우

 

따라서 $F(N, K) = K*F(N-1, K-1) + (K-1)*F(N-1, K)$ 와 같은 식을 얻을 수 있고 이를 구해주면 문제를 해결 할 수 있습니다.

다만 이때 기저케이스로 조심해야하는 부분이 칠해야하는 색 K가 칠해져야할 정점들 N보다 많으면 return 0을 해줘야 한다는 점 입니다.

K개의 색 전부를 사용해야 함으로 이 점을 조심해야합니다.

 

1135 뉴스 전하기

트리 dp 문제입니다.

트리 아래로 뉴스를 전달 할 때, 가장 오래 걸리는 서브 트리부터 뉴스를 전달해주어야 최소값을 얻을 수 있습니다.

dp(u) := u를 루트로 하는 서브트리의 답

이때 가장 오래 걸리는 서브트리 부터 뉴스를 전달해야 함으로 $dp(v_{1}) \geq dp(v_{2}) \geq ... \geq dp(v_{k})$ 라고 한다면

$dp(u) = \max\limits_{1\leq i\leq k} dp(v_{i} + i)$ 임을 알 수 있습니다.

이때 dp의 값은 단순히 깊이가 깊다고 큰게 아니라는 점에 주의하여 구현해주셔야 합니다.

 for (int nxt:G[u]) {
    tmp.push_back(dp(nxt));
  }
  sort(tmp.begin(), tmp.end());
  reverse(tmp.begin(), tmp.end());

이렇게 바로 아래 서브트리의 dp값을 구해서 정렬하고 이 중 MAX를 찾아주면 문제를 해결 할 수 있습니다.