그냥 하는 노트와 메모장

* BOJ 1742 레이싱 결과[분류 : 다이나믹 프로그래밍, DAG, 그래프 이론, 조합론] [풀이] 1. [그래프 구조] 먼저 구성되는 컴포넌트의 구조는 양방향 그래프가 아닌 DAG(Directed Acyclic Graph)이어야 한다. 즉, 사이클이 존재하면 모순이 발생하므로 경우의 수는 0이 돼야 한다. 2. [컴포넌트 집합] 하나의 컴포넌트에 여러 노드가 존재할 수 있다. 따라서 같은 컴포넌트에 있는 노드를 집합으로 둔다. 3. [진출 간선?] 나는 경기결과를 작성할 때 맨 뒤에서 시작해서 작성하는 걸 채택했다. 구성되는 dag 컴포넌트에서 진출 간선이 0인 것들부터 넣는 방식을 생각해보자. 진출 간선이 없다는 의미는 더 이상 자신이 반드시 이기는 상대가 존재하지 않는다는 뜻이다. 따라서 리프(..

그래프 이론 + dp 문제의 다소 신기한 문제라 포스팅한다. i가 3이상인 구간에 대해서 아래의 공식이 성립한다. 아래 그림을 보자. 먼저 dp[i-1]을 설명한다. i이지만 i->k가 아닌 경우 > 0 k로 가는 경우는 없이 세는 것이다. i이고 i->k인 경우 > 마찬가지로 k의 후보는 0~i-1이므로 총 i개, k에 대해 i를 연결하고 i에 대해 k를 연결하면 나머지 i-2개에 대해 재배정이 되지 않도록 하는 방법의 수는 dp[i-2]가 된다. 따라서 i*dp[i-2]가 된다. 이 이후로 사이클 3개, 4개에 대해서 다루지 않는 이유는 이미 dp[i-1]에 포함되어 있기 때문이다. k가 i를 가리키고 있는 와중에 나머지 i-1개의 정점들 간의 재배정되지 않는 경우 안에 이 것이 포..