요리 강좌 > 문제은행

본문 바로가기


문제은행

3080 : 요리 강좌

제한시간: 0Sec    메모리제한: 0mb
해결횟수: 0회    시도횟수: 0회    채점준비중입니다.



여러분은 요리에 관심이 많아 요리 자격증을 취득하려고 한다. 요리 자격증을 취득하기 위해서는 총 M개의 강좌를 순서대로 한 번씩만 수강해야 한다. 이 요리 강좌는 N개의 학원에서 수강할 수 있는데, 학원마다 강좌별 수강비용은 다를 수 있다.

 

아래 표는 M=5, N=4인 경우, 학원 별, 강좌별 수강비용의 예를 보여준다.

08b6f023ea4f0ddc33a2459594e06b23_1502450
 

여러분은 비용을 줄이기 위해 중간에 학원을 변경할 수 있는데, 학원을 변경 할 때마다 T의 추가 비용이 든다. 단, 학원 변경은 다음 규칙을 지켜야 한다.

 

(a) 하나의 학원에서 연속으로 수강할 수 있는 강좌의 수는 최소 S개, 최대 E개다. S=2이고 E=3이라고 가정하자. 강좌1을 학원1에서 수강했다면, 강좌2는 무조건 학원1에서 수강해야 하고, 강좌3은 학원1에서 수강할 수도 있고 다른 학원에서 수강할 수도 있다. 만약 강좌1부터 강좌3을 학원1에서 수강했다면, 강좌4는 무조건 다른 학원에서 수강해야 한다.또한, S=1이고 E=2인 경우, 강좌1과 강좌2를 학원3에서 수강하고, 강좌3과 강좌4를 학원1에서 수강하고, 강좌5를 다시 학원3에서 수강하는 것도 가능하다.

 

(b) 학원마다 직전 강좌를 특정한 학원에서 수강한 학생은 받지 않는데, 이를 ‘불허용 학원’이라고 하자. 각 학원마다 불허용 학원은 하나씩 존재한다.

예를 들어, 아래 표의 학원1에 대한 정보는 학원2→학원1로 변경하는 것은 불가능하다는 것을 의미한다. 단, 학원2→학원4→학원1처럼 학원4 수강을 거쳐 변경하는 것은 가능하다.

08b6f023ea4f0ddc33a2459594e06b23_1502450

예를 들어, S=2, E=3, T=2 이고, 위 수강비용 표와 불허용 학원 표가 주어 졌을 때, 강좌 순서대로 수강하는 학원의 번호가
예1) 1 → 1 → 1 → 1 → 3 인 경우, 규칙 (a)에 위배되어 수강이 가능하지 않다.

예2) 2 → 2 → 1 → 1 → 1 인 경우, 규칙 (b)에 위배되어 수강이 가능하지 않다.

예3) 3 → 3 → 1 → 1 → 3 인 경우는 가능한 수강 방법이고, 전체 비용은 1+8+T+1+3+T+2 = 19이다.
예4) 1 → 1 → 1 → 3 → 3 인 경우는 가능한 수강 방법이고, 전체 비용은 1+2+1+T+1+2 = 9이다.

 

강좌 비용, 강좌 선택에 필요한 규칙 정 보가 주어졌을 때, 모든 강좌를 순서대로 수강하기 위해 필요한 최소 비용을 구하시오.
 


표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 학원의 개수 N과 강좌 개수 M(3≤N≤3,000, 1≤M≤3,000, N×M≤3,000,000), 학원 한 곳에서 연속 수강 가능한 최소 강좌 개수 S와 최대 강좌 개수 E(1≤S≤E≤M), 그리고 학원 변경 비용 T(0≤T≤35,000)가 주어진다. 다음 N개의 줄에는 각 학원의 강좌별 수강비용이 주어진다. (수강비용은 1 이상 35,000 이하이다.) 처음 줄에는 학원1의 M개의 수강비용이 강좌 순서대로 공백을 사이에 두고 주어지고, 그 다음 줄부터 학원2, 학원3, ... , 학원N의 정보가 한 줄에 하나씩 순서대로 주어진다. 그 다음 N개의 줄에는 학원마다 불허용 학원 번호가 순서대로 주어진다.


표준 출력으로 최소 비용을 출력한다.

부분문제의 제약 조건
● 부분문제 1: 전체 점수 100점 중 13점에 해당하며 N,M≤50 이다.
● 부분문제 2: 전체 점수 100점 중 9점에 해당하며 N,M≤300 이다.
● 부분문제 3: 전체 점수 100점 중 11점에 해당하며 N≤3,000, M≤300 이다. 
● 부분문제 4: 전체 점수 100점 중 23점에 해당하며 N≤300, M≤3,000 이다. 
● 부분문제 5: 전체 점수 100점 중 44점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.

[Copy]
4 5 2 3 2 
1 2 1 3 8 
1 2 3 7 2 
1 8 8 1 2 
10 1 1 8 8 
2 
3 
4 
3
[Copy]
9


[Copy]
4 5 1 1 0 
1 2 1 3 8 
1 2 3 7 2 
1 8 8 1 2 
10 1 1 8 8 
2
3 
4 
3
[Copy]
9




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.