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 를 기준으로 좌/우로 나누는 건줄 알았다.

그래서 문제를 이해해서 제대로 못 풀었다.

그리고 해답을 얼핏 보고 아하.. 하고 다시 푼 문제.





반응형

설정

트랙백

댓글