카드 배열 > 문제은행

본문 바로가기


문제은행

2575 : 카드 배열

제한시간: 1Sec    메모리제한: 0mb
해결횟수: 29회    시도횟수: 223회   



하나의 숫자가 쓰여 있는 카드가 N장이 있다. 쓰여 있는 숫자는 0부터 N-1사이의 숫자 중 하나이며, 모든 카드의 숫자는 서로 다르다.


이 카드들 중에서 k개의 카드를 선택하여 배열한 순서를 CK-1, CK-2, ..., C0라고 하자. 이렇게 배열된 k장의 카드가 N진법의 수를 나타낸다고 하면, 카드 Ci는 N진법의 수에서의 한 자리수를 의미하며 그 자릿수의 값은 Ci×Ni이다.
그러므로 배열된 카드의 수의 값은 Ck-1×Nk-1+Ck-2×Nk-2+...+C0×N0이 된다.


배열되는 카드들 사이에는 Ci>Cj형태의 제약조건이 주어진다. 제약조건 Ci>Cj는 Ci숫자가 Cj숫자보다 커야함을 의미한다. 단, i≠j.


예를 들어, N=4, k=3인 경우에 C2>C0, C0>C1의 제약조건이 주어졌다고 하자. 이 경우 가능한 카드의 배열은 (2, 0, 1), (3, 1, 2), (3, 0, 1), 그리고 (3, 0, 2) 네 가지 경우가 있다.


이 네 개의 경우들 중에서 가장 큰 수가 되는 카드의 배열은 (3, 1, 2)이고 이 수의 값은 3×42+1×41+2=54이다. 또한, 가장 작은 수가 되는 카드 배열은 (2, 0, 1)이고 이 수의 값은 2×42+0×41+1=33이다.


전체 카드의 수와 선택할 카드의 수 그리고 제약조건들이 주어질 때, 제약조건을 만족하는 카드배열 중에서 가장 큰 값을 갖는 카드배열과 가장 작은 값을 갖는 카드배열을 찾아서 그 값의 차이를 구하는 프로그램을 작성하시오.


입력의 첫 번째 줄에는 전체 카드의 수를 나타내는 N과 선택하는 카드의 수 k와 제약조건의 수 P가 하나의 빈칸을 사이에 두고 주어진다. 단, 3≤k≤300,000, 0≤P≤1,000,000이다. 

두 번째 줄부터 P개의 줄에는 각 줄마다 하나의 제약조건을 나타내는 두 개의 정수 a,b가 하나의 빈칸을 사이에 두고 주어진다. 이는 제약조건 Ca>Cb를 의미한다.


제약조건을 만족하는 카드배열 중에서 가장 큰 값을 갖는 카드배열과 가장 작은 값을 갖는 카드배열을 찾고, 그 값의 차이를 1,000,000,007로 나눈 나머지를 출력한다. 단, 제약조건을 만족하는 카드의 배열이 존재하지 않는 경우는 없다.

[테스트 데이터 조건]
• 전체 테스트 데이터의 20%는 N, k≤11.
• 전체 테스트 데이터의 40%는 N, k≤10,000.

[Copy]
4 3 2
2 0
0 1
[Copy]
21




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.