DOJ logoDOJ
문제
최근 추가된 문제들저장한 문제문제집
카테고리DLC대회그룹팀게시판
랭킹
문제 풀이 랭킹스트릭 랭킹DOJ Power 랭킹
현황
문제 제안로그인회원가입
DOJ logoDOJ

OI 서브태스크 채점, Elo 레이팅, Discord 계정 연동을 갖춘 커뮤니티 온라인 저지.

문제
문제 목록카테고리
커뮤니티
대회랭킹게시판공지사항외부 대회 개최이용 안내
계정
로그인회원가입채점 현황
정책
이용약관DLC 이용 규칙개인정보 처리방침API 사용 설명서언어별 채점 환경대회 순위 보상레이팅과 퍼포먼스
© 2026 DOJ
모든 권리 보유
해설

비료 납품

문제로 돌아가기

해설

합성을 ttt번 하면 암모니아를 2t2t2t통 얻는다. 필요한 최소 합성 횟수는 t=⌈K/2⌉t=\lceil K/2\rceilt=⌈K/2⌉이다. 그보다 많이 합성하려면 더 많은 원료가 필요하므로 최소 비용을 낮출 수 없다. 따라서 질소 ttt통과 수소 3t3t3t통을 사는 문제를 각각 풀면 된다.

각 원료를 통당 가격이 낮은 거래처부터 재고 한도까지 구매한다. 더 싼 거래처에 재고가 남았는데 더 비싼 거래처에서 구매했다면, 그중 한 통을 더 싼 곳에서 사도록 바꿀 수 있다. 이 교환은 구매 총량을 유지하면서 비용을 줄인다. 가격이 같은 거래처의 구매 순서는 비용에 영향을 주지 않는다. 따라서 통당 가격을 오름차순으로 정렬하고, 각 거래처에서 남은 필요량과 재고량 중 작은 만큼 사면 최적이다. 어느 원료든 재고를 모두 사용하고도 필요량이 남으면 -1을 출력한다.

M=kn+khM=k_n+k_hM=kn​+kh​라 하면 시간 복잡도는 O(Mlog⁡M)O(M\log M)O(이고 공간 복잡도는 이다. 구매하는 양은 총 통이고 통당 가격은 최대 이므로, 가능한 최소 비용의 최댓값은 이다.

Solution written by GPT

M
log
M
)
O(M)O(M)O(M)
4t≤2⋅1094t\leq 2\cdot 10^94t≤2⋅109
10610^6106
2⋅10152\cdot 10^{15}2⋅1015