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인 경우도 존재할수 있으므로 이 경우에 대한 예외처리가 필요하다. 이때는 묶음으로 사지 않고 모두 낱개로 사는것이 최적이다.
코드
(다이아몬드 이상은 코드 첨부 생략)
ps/problems/boj/18186.txt · 마지막으로 수정됨: 2022/01/18 15:07 저자 teferi
토론