프로그래밍
Dynamic Programming - Building Bridges, Balanced Partition.
아자
2012. 8. 6. 10:54
1) Building Bridges
문제내용:
가운데로 강이 지나가는 2차원 지도가 있다. 강 북쪽과 남쪽으로 각각 N 개의 도시가 있다.
이 N 개의 도시를 A(1)...A(N), B(1)...B(N) 이라고 한다.
이 도시는 순서대로 위치해 있지는 않다. (즉 A(1) 옆에 A(2) 가 있는게 아니라는 말)
강 북쪽과 남쪽은 연결하는 다리를 건설하고자 하는데,
다리의 건설은 A(k) 와 B(k) 만 연결할 수 있다.
이 때, 가장 다리를 많이 놓을 수 있는 갯수는 몇 개 인가?
설명이 은근히 길다.
그림으로 그리고 싶지만, 잘 찾지도 못하겠고 그리기도 귀찮아서 패스.
- Balanced Partition
문제:
N 개의 정수를 가진 집합을 2개의 Subset S1, S2 로 나누었을 때, |Sum(S1) - Sum(S2)| 의 최소값을 구하라.
사실 이 문제는 내가 못 풀었다.
Subset 을 나누는 데, 단순히 한 Element 를 기준으로 좌/우로 나누는 건줄 알았다.
그래서 문제를 이해해서 제대로 못 풀었다.
그리고 해답을 얼핏 보고 아하.. 하고 다시 푼 문제.
반응형