22/9/21 PS

연습셋 망하고 열심히 해야겠다는 생각이 들었다.

BOJ 12845 모두의 마블(S3)

max 레벨 * (n - 1) + 나머지 모든 레벨 합 이 답이다.

 

BOJ 25197 합주단 곰곰(G3)

어떤 한 곰곰의 색이 정해졌을 때, 다른 한 곰곰이 그 색과 같은 확률은 1/k,

이런 두 곰곰을 선택할 수 있는 횟수는 nC2 이므로, 기댓값의 선형성에 의해, k*nC2 가 답이다.

 

BOJ 12842 튀김 소보루(S2)

나는 이분탐색으로 풀었다. wbcho0504님 코드를 보니, set<pair<int, int>> 를 이용해 구현하여 풀 수도 있는 것 같다.

일단 어떤 시간 T를 기준으로 n-s개의 튀김 소보루를 다 먹거나, 아니게 되므로 이분 탐색으로 해당 갯수의 소보루를 다 먹는 최소의 T를 찾자. 찾은 T와 n-s의 차이를 이용해서 마지막으로 소보루를 집은 사람을 찾으면 된다.

 

BOJ 25196 숲속에서 새 구경하기(G1)

L = lcm(Av, Bv, Cv), l = lcm(Av, Bv) 라 하자.

[min(Av, Bv), min(Av, Bv)+l) 을 모두 보면서,  첫 번째 새와 두 번째 새를 동시에 볼 수 있는 시간을 저장해둔다.

[0, L)에서 저장해둔 시간만 보면서 세 번째 새도 볼 수 있는지 찾으면 된다.

 

BOJ 25198 곰곰이의 심부름(G1)

주어진 그래프는 트리이므로, S->C, C->H인 경우를 각각 DFS로 최단 경로를 찾아주고 역추적으로 경로를 저장해놓는다. S->C 의 최단 경로에는 중복되는 정점이 없으므로, 최단 경로를 구성하는 정점의 개수를 n이라고 하면, nC2개의 순서쌍을 답에 추가할 수 있다. C->H의 최단 경로도 마찬가지로 추가해줄 수 있다.

관건은 S->C에서 하나, C->H에서 하나를 뽑는 경우인데, 이는 각 경로의 중복되는 정점을 뺀 정점 개수의 곱을 추가해주면 된다.

 

BOJ 3078 좋은 친구(G4)

이름이 2글자~20글자이므로, 이름의 길이에 대응하는 큐를 18개 만들어서, 최근 k개의 친구만 들고 있으면 된다.