비트망고 풀이해줌 3번 푼사람 나 알려줘

[익명(210.91)]

1 

무지성 구현 

2 

첨에 스위핑인줄 알고 시간 ㅈㄴ 잡아 먹음 

원갯수가 천개 이하라 완탐 해도 될듯?

난 혹시 몰라 분리집합으로 시간 조금이라도 더 줄임

3

트리dp 같은데 못 풂

4

bfs + 비트마스킹

[익명(210.222)]

3번 DP 종류 같은데 씨 ㅡ발 dp 4번째부터 막힘 1 4 10 19 31 ???????????

[익명(210.91)]

규칙 없을껄? 방향 그래프라 그려지는게 다 다를텐데

[익명(210.222)]

같은 숫자의 총 개수를 구하고 이 개수로 경우의 수를 구하는거임 ㅄ아

[익명(210.222)]

방향그래프 치자 하면 본 문제에서 왜 씨 ㅡ발 3번째 노드가 0번째 노드랑 매칭됨?

[익명(210.222)]

i < j 조건 없잖아 병 ㅡㅅ니아

[익명(210.91)]

0 0 1 답 뭐 나와야댐?

[익명(210.91)]

니 말대로라면 0 두개라 1 나와야댐?

[익명(210.222)]

0 0 1이면 0번째 노드랑 1번째 노드가 서로 사이클 발생하지 병 ㅡ신아 2번째 노드는 혼자 있는 찐따고

[익명(210.222)]

0 0 0 1이면 0, 1, 2 번째 노드가 서로 싸이클 발생하니까 0-1 1-2 0-2 0-1-2 결국 4개임

[익명(210.91)]

그러네 규칙있네 머야 그럼 개줫밥이엿네 트리dp가 아니라 확률dp로 풀면 끝나는거엿네

[익명(210.91)]

확률이 아니라 조합 ㅇㅅㅇ

[익명(210.222)]

아 그런거였어 씨 ㅡ발? 4번째부터 출력 예상 값이 안나와서 ㅈㄴ 답답했음

[익명(210.222)]

4번은 왜 bfs냐? 백트래킹 해야하는데

[익명(210.91)]

최소 갯수라 bfs가 빠르지않나

[익명(125.187)]

3번 숫자 같은거 끼리 그룹지어서 경우의 수 세는 방법으로 풀었는데 맞는지는 모름 ㅇㅅㅇ

[익명(210.222)]

등차급수로 풀었냐? 나 DP로 등차급수 구하려다가 막혀서 ㅈ같음

[익명(125.187)]

같은 그룹마다 for c = 2 to n: combination(n, c) * (c - 1)! 계산함

[익명(210.222)]

ㅇㅇ 근까 결과물이 등차급수잖음

[익명(125.187)]

수학 잘 몰?루 ㅇㅅㅇ

[익명(223.33)]

2번 수학임 ㅋㅋ

[익명(210.91)]

당연히 안에 있는 원 판단하는건 수학이지

[익명(182.225)]

와 애들 개 잘하네 난 어려워서 포기했는 데