학생회 자선 아침 식사

면접 대비

시간 제한1초메모리 제한128 MB

요약

티켓 가격 네 개와 목표 금액이 주어질 때, 목표 금액을 정확히 만드는 네 색 티켓 개수 조합을 모두 출력하고, 조합 수와 최소 티켓 수를 구한다.

난이도: 쉬움10점 중 3점
유형: 완전 탐색, 구현, 수학, 정렬
정답자: 아직 제출이 없습니다

문제

학교 학생회가 자선 아침 식사 행사를 열려고 합니다. 학년이 높은 학생일수록 더 지혜롭고 형편도 넉넉하다는 이유로, 학생회는 티켓 가격을 재학 연차에 따라 정하기로 했습니다. 1학년은 분홍색(PINK) 티켓, 2학년은 초록색(GREEN) 티켓, 3학년은 빨간색(RED) 티켓, 4학년은 주황색(ORANGE) 티켓을 삽니다.

발행한 티켓은 모두 판매된다고 가정합니다. 네 색깔 티켓의 가격은 서로 다릅니다.

각 색 티켓을 몇 장씩 팔면 목표 모금액을 정확히 만들 수 있는지, 그 모든 조합을 구하세요. 하나의 조합은 음이 아닌 정수 $p, g, r, o$ (각각 PINK, GREEN, RED, ORANGE 티켓의 장수)로 나타내며 다음을 만족합니다.

$p \times \text{PINK} + g \times \text{GREEN} + r \times \text{RED} + o \times \text{ORANGE} = \text{목표 금액}$

목표 금액을 만드는 조합이 적어도 하나 존재함이 보장됩니다.

입력

PINK, GREEN, RED, ORANGE 티켓의 가격을 이 순서대로 입력하고, 이어서 티켓 판매로 모아야 할 정확한 금액을 입력합니다. 다섯 개의 값은 모두 양의 정수이며, 각각 한 줄에 하나씩 주어집니다.

출력

목표 금액을 정확히 만드는 모든 조합을, 장수 $(p, g, r, o)$ 의 오름차순(먼저 PINK 장수, 같으면 GREEN, 그다음 RED, 마지막으로 ORANGE 장수)으로 사전식 정렬하여 한 줄에 하나씩 다음 형식으로 출력합니다.

# of PINK is p # of GREEN is g # of RED is r # of ORANGE is o

그다음 줄에 찾은 조합의 총 개수를 Total combinations is N. 형식으로 출력합니다.

마지막 줄에는 목표 금액을 모으는 데 필요한 최소 티켓 수(모든 유효한 조합에 대한 $p + g + r + o$ 의 최솟값)를 Minimum number of tickets to print is M. 형식으로 출력합니다.

예제1

예제 1

입력

예상 출력

# of PINK is 0 # of GREEN is 0 # of RED is 1 # of ORANGE is 0
# of PINK is 1 # of GREEN is 1 # of RED is 0 # of ORANGE is 0
# of PINK is 3 # of GREEN is 0 # of RED is 0 # of ORANGE is 0
Total combinations is 3.
Minimum number of tickets to print is 1.