[usaco] 2.2 Subset Sums - usaco
2009.08.11 23:08 Edit
1~n 까지의 숫자를 두 그룹으로 나눠서
그 두 그룹의 합이 같을 때
나눌 수 있는 경우의 수를 세는 문제이다.
처음엔 dfs로 다 세어볼까 했지만 n이 39까지 나와야하기 때문에
2^39는 안나오기 때문에 포기하고
DP로 생각을 했다.
DP는 좀 어려운듯... 20분 정도 걸렸다. -_-;;
좀 더 빨리 풀 수 있어야 탑코더 옐로우도 가고 그럴듯...
그 두 그룹의 합이 같을 때
나눌 수 있는 경우의 수를 세는 문제이다.
처음엔 dfs로 다 세어볼까 했지만 n이 39까지 나와야하기 때문에
2^39는 안나오기 때문에 포기하고
DP로 생각을 했다.
DP는 좀 어려운듯... 20분 정도 걸렸다. -_-;;
좀 더 빨리 풀 수 있어야 탑코더 옐로우도 가고 그럴듯...
