막대기 > 문제은행

본문 바로가기


알고리즘 다이나믹2

2635 : 막대기

제한시간: 1Sec    메모리제한: 32mb
해결횟수: 134회    시도횟수: 579회   



다양한 길이의 막대기를 가지고 즐길 수 있는 게임이 있다. 게임을 시작하기 전에 간격이 L 인 두개의 평행한 수평선을 책상 위에 긋고, 막대기의 양 끝이 각 수평선에 하나씩 위치하도록 놓는다.


여러 개의 막대기 끝이 수평선 위의 한 점에서 만날 수는 있지만, 두 막대기가 완전히 겹쳐져 있는 경우는 없다. 놓여 있는 각 막대기는 (t, d) 로 표현된다. 여기서 t 는 위쪽 수평선에서의 좌표이고 d 는 아래쪽 수평선에서의 좌표이다. 아래 그림 1 에서 막대기 a는 (1, 0), 막대기 b는 (6, 0)으로 표시된다.


7ce7f2eba5731c8babe39036322897a0_1449821 


게임은 책상에 놓여 있는 막대기들 중 일부를 들어내어 남아 있는 막대기들이 다음의 세 조건을 모두 만족하는 하나의 지그재그 선이 구성되도록 하는 것이다: (1) 막대기들은 끝점을 제외하곤 서로 교차하지 않는다. (2) 세 개 이상의 막대기 끝이 한 점에서 만나지 않는다. (3) 모든 막대기는 연결되어 있다.


이 게임의 승자는 길이가 가장 긴 지그재그 선을 만든 사람이다. 지그재그 선의 길이는 막대기 길이들의 합이며, 각 막대기의 길이는 양 끝점의 수평 거리와 수직 거리를 더한 값으로 계산한다. 즉, 막대기 (t,d)의 수평 거리는 t 와 d 사이의 절대 값 |t-d|이고, 수직 거리는 두 수평선 사이의 간격인 L 이다. 위 그림에서 각 막대기의 길이는 다음과 같다.


7ce7f2eba5731c8babe39036322897a0_1449821 


예를 들면, 그림 1에서 막대기 a, b, e 만 남겨진 경우는 세 조건을 모두 만족하는 지그재그 선이며, 길이는 17 = 4+9+4 이다. 막대기 c, e 만 남겨진 경우도 세 조건을 모두 만족하는 지그재그선이며, 길이는 10 = 6+4 이다. 막대기 b, c 만 남겨진 경우는 조건 (1)에 위배되고, 막대기 c, d, e 만 남겨진 경우는 조건 (2)에 위배되고, 막대기 a, b, g 만 남겨진 경우는 조건 (3)에 위배된다. 길이가 가장 긴 지그재그 선은 막대기 c, d, f, g 로 구성되며, 길이는 20 = 6+4+7+3 이다.


막대기들의 초기 상태가 주어져 있을 때, 가장 긴 지그재그 선의 길이를 구하기 위한 프로그램을 작성하시오.


입력파일의 첫 줄에는 막대기의 개수와 수평선 사이의 간격을 나타내는 두 개의 정수 N과 L이 주어진다. 여기서 N은 1이상 100,000이하이고, L은 1이상 1,000,000이하이다.

그 다음 N 개의 줄에는 각 줄마다 막대기 (t,d)를 나타내는 두 개의 정수 t와 d가 빈칸을 사이에 두고 주어진다. 여기서 t와 d는 각각 0 이상 100,000,000 이하이다. 입력으로 들어오는 막대기들 중 어떤 두 막대기도 완전히 겹쳐져 있는 경우는 없다.

<제약조건>
• 부분문제 1:& nbsp; 전체 점수 100점 중 11점에 해당하는 데이터에 대해 N≤20이다.
• 부분문제 2:  전체 점수 100점 중 13점에 해당하는 데이터에 대해 N≤100,000이고 막대기 끝점의 좌표는 1,000이하이다.
• 부분문제 3:  전체 점수 100점 중 16점에 해당하는 데이터에 대해 N≤100이다.
• 부분문제 4:  전체 점수 100점 중 22점에 해당하는 데이터에 대해 N≤1,000이다.
• 부분문제 5:  전체 점수 100점의 38점에 해당하는 데이터에 대해 추가적인 제한 조건은 없다.
중간 계산 결과와 출력할 값이 32비트 정수형 범위를 벗어날 수 있으니 64비트 정수형을 이용할 것을 권장한다.


주어진 입력에 대해 길이가 가장 긴 지그재그 선의 길이를 한 줄에 출력한다.

[Copy]
7 3
1 0
6 0
2 5
4 5
6 5
4 8
8 8
[Copy]
20


[Copy]
4 5
1 1
3 2
3 4
5 5
[Copy]
12




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.