사용자 도구

사이트 도구


ps:problems:boj:18186

라면 사기 (Large)

ps
링크acmicpc.net/…
출처BOJ
문제 번호18186
문제명라면 사기 (Large)
레벨다이아몬드 4
분류

그리디

시간복잡도O(n)
인풋사이즈n<=10^6
사용한 언어Python
제출기록149440KB / 968ms
최고기록968ms
해결날짜2022/01/18

풀이

  • 라면 사기 (Small)의 라지 버전.
  • n의 범위가 커졌고 라면의 가격이 일반화되었지만, 알고리즘 자체는 라면 사기 (Small)과 동일하다. 오히려 문제가 일반화되면서 더 쉬워진 느낌도 있다. 라면 묶음들의 가격이 3,5,7로 주어졌던 라면 사기 (Small)에서는 2개 묶음 2개를 사는것과 1개묶음과 3개묶음을 사는 것이 동일한 가격이라는 중요한 단서를 눈치채기 어려웠는데, B, B+C, B+2C원으로 주어진 이 문제에서는 여기에 의미가 있을 것이라는 점을 눈치채기가 오히려 더 쉬워졌다.
  • 풀이 자체는 동일하므로 라면 사기 (Small) 참고.
  • 다만 이 문제에서는 B>C인 경우도 존재할수 있으므로 이 경우에 대한 예외처리가 필요하다. 이때는 묶음으로 사지 않고 모두 낱개로 사는것이 최적이다.

코드

(다이아몬드 이상은 코드 첨부 생략)

토론

댓글을 입력하세요:
H Y X M H
 
ps/problems/boj/18186.txt · 마지막으로 수정됨: 2022/01/18 15:07 저자 teferi