서울에서 경산까지 > 문제은행

본문 바로가기


문제은행

3074 : 서울에서 경산까지

제한시간: 1Sec    메모리제한: 128mb
해결횟수: 16회    시도횟수: 53회   



배우 한정올 씨는 이번 여름에 서울에서 경산까지 자선 여행을 하면서 모금활동을 진행할 계획이다. 자선 여행에서 거쳐 가게 될 도시의 개수와 순서는 미리 정해져 있으며, 자선 여행은 서울에서 시작하여 각 도시를 정해진 순서대로 단 한 번씩 방문한 후 경산에서 끝난다. 서울을 제외한 도시의 개수를 N이라 하자. 이 때 서울에서 두 번째 도시까지 가는 구간을 구간 1, 두 번째 도시부터 세 번째 도시까지 가는 구간을 구간 2와 같이 부르기로 하며, 마지막 목적지인 경산에 도착하는 구간을 구간 N이라 하자. 즉, 구간의 전체 개수는 N이다. 구간 사이의 이동은 도보 혹은 자전거 어느 한 쪽을 이용하게 되는데, 각 구간에는 도보로 이동할 때 걸리는 시간(분), 이 때 얻게 되는 모금액(원), 자전거로 이동할 때 걸리는 시간(분), 이 때 얻게 되는 모금액(원)이 정해져 있다.

 

예를 들어, 서울과 경산 사이에 2개의 도시가 있는 다음과 같은 경우(N = 3)를 생각해 보자.

08b6f023ea4f0ddc33a2459594e06b23_1502448

인접한 도시 사이를 도보로 이동하는지 자전거로 이동하는지에 따라 전체 모금액이나 걸리는 시간에 차이가 생기게 된다. 한정올 씨는 전체 모금액을 가능한 많이 얻는 방법을 찾고 싶어 한다. 위의 예에서는 시간이 충분하다면 모든 구간을 도보로 이동하는 것이 모금액을 최대로 하는 방법이며, 모금액은 200+370+250 = 820원, 여행에 걸리는 시간은 500+800+700 = 2,000분이다.

 

그러나 한정올 씨는 바쁜 스케줄로 인해 자선 여행을 위해 보낼 수 있는 시간이 K분(K는 자연수)으로 한정되어 있다. 위의 예에서 만약 K=1.650이라면, 1, 2번 구간은 도보로 이동하고 3번 구간은 자전거로 이동하여 모금액을 660원으로 하는 것이 가장 좋은 방법이며, 이 때 걸리는 시간은 1,600분이다.

 

위와 같이 각 구간별로 도보 및 자전거로 이동하는 경우 걸리는 시간과 모금액이 주어질 때, 제한시간 이내로 서울에서 경산까지 여행하면서 모금할 수 있는 최대 금액을 찾는 프로그램을 작성하시오. (제한시간 이내에 여행하는 방법은 항상 존재한다.)
 


표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 두 자연수 N과 K가 공백으로 분리되어 주어진다(3 ≤ N ≤ 100, 0 < k ≤ 100,000).
두 번째 줄에는 구간 1을 도보로 이동할 때 걸리는 시간(분), 이 때 얻게 되는 모금액(원), 자전거로 이동할 때 걸리는 시간(분), 이 때 얻게 되는 모금액(원)을 나타내는 네 개의 자연수가 차례로 공백으로 분리되어 주어진다. 세 번째 줄부터 N+1번 째 줄도 마찬가지 형식으로 각 줄마다 네 개의 자연수가 주어지며, 입력은 총 N+1줄로 구성된다. 두 번째 줄부터 N+1번 째 줄에 주어지는 숫자들 중 시간을 나타내는 숫자(각 줄의 첫 번째, 세 번째 숫자)는 10,000 이하의 자연수, 모금액을 나타내는 숫자(각 줄의 두 번째, 네 번째 숫자)는 1,000,000 이하의 자연수들이다.


표준 출력으로 K분 이내로 여행하면서 모금할 수 있는 최대 금액을 출력한다. (K분 이내에 여행하는 방법은 항상 존재한다.)

부분문제의 제약 조건
● 부분문제 1: 전체 점수 100점 중 29점에 해당하며 N의 범위를 N ≤ 20으로 제한한다.
● 부분문제 2: 전체 점수 100점 중 71점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.

[Copy]
3 1650
500 200 200 100
800 370 300 120
700 250 300 90
[Copy]
660


[Copy]
4 3000
1000 2000 300 700
1100 1900 400 900
900 1800 400 700
1200 2300 500 1200
[Copy]
5900


[Copy]
3 600
500 150 200 1000
100 835 200 324
200 125 300 900
[Copy]
2735




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.