BOJ 1007 - 벡터 매칭(Vector Matching)

문제 :
https://www.acmicpc.net/problem/1007

점이 n 개 있으면 n / 2개의 벡터를 만들 수 있다. 이 n / 2개의 합벡터를 생각해보면, n / 2개의 점은 더해지고, 나머지 n / 2개의 점은 빼진다(벡터 하나를 u - v로 표현).

즉, 이 문제는 n개의 점에서 합벡터를 만들 때 더해질 점을 n / 2개 고르는 문제로 생각 할 수 있다. n이 20이라 완전탐색을 짜도 n C n/2 만큼 탐색하게 되므로 시간안에 들어올 수 있다.

소스 : http://ideone.com/ctYs2L

댓글

댓글 쓰기

이 블로그의 인기 게시물

BOJ 11478 - 서로 다른 부분 문자열의 개수

길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP $O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 $O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 $O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) :  http://ideone.com/bugbDy 코드 (해싱) :  http://ideone.com/hkjw5n
계속 읽기

repeated squaring

https://www.acmicpc.net/problem/1533 최대 가중치 5인데 한 정점을 정점 다섯개로 치환하고 모든 간선의 가중치가 1인것처럼 만든다. 그런식으로 만든 인접행렬을 거듭제곱하면 답을 구할 수 있다. http://codeforces.com/problemset/problem/621/E
계속 읽기