[백준 / BOJ] 15970 화살표 그리기

문제

출처 : www.acmicpc.net/problem/15970

15970번: 화살표 그리기

점들의 색깔과 위치(x좌표)가 주어진다.

 

각각의 점을 가까우면서 같은색깔인 점에 연결할려할때, 연결한 선의 최대거리를 구하는 문제다.

 

풀이

N이 크지않아 완전탐색으로도 풀리는문제다.

 

문제를 잘 읽지않고 점들의 색깔이 항상 2개인줄 알고풀다가 몇번 틀렸었다.

 

1. 점들을 입력받을때, 같은 색깔은 같은 벡터에 들어가도록 입력받는다.

 

2. 각 벡터를 N번 정렬한다.

 

3. 현재 점의 idx에서 idx+1위치와, idx-1위치의 거리를 비교해가며 작은 값을 더해주는걸 색깔만큼 반복한다. (거리순 으로 정렬했기 때문에 idx-1, idx+1보다 가까운 점은 있을수없다.)

소스코드

https://github.com/devxb/JJUNalgo/blob/master/15970%20%ED%99%94%EC%82%B4%ED%91%9C%20%EA%B7%B8%EB%A6%AC%EA%B8%B0/main.cpp

devxb/JJUNalgo