반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- softeer
- 연결요소
- @P0
- dfs
- 오퍼레터
- 처우산정
- 처우협의
- 물채우기
- 13908
- 성적평가
- compose
- 기술면접
- 백준
- msSQL
- 퇴사통보
- 매개변수탐색
- upper_bound
- BOJ
- Kafka
- 경력
- incr
- BFS
- OFFSET
- 이분탐색
- 6987
- 소프티어
- Docker
- boj #19237 #어른 상어
- 파라메트릭
- 백트래킹
Archives
- Today
- Total
기술 블로그
18185번 라면 사기 (Small) 본문
728x90
반응형
https://www.acmicpc.net/problem/18185
Greedy 그리디 탐욕 boj 백준 복습 필수 추천 dp 수학 등차수열
무조건 3개의 공장에서 라면을 구매할 수 있는 경우가 있으면, 3개 공장을 먼저 처리하는 문제인줄 알았다.
즉, 3 → 2 → 1 이런 순서로 진행하는 줄 알았다.
하지만, 반례가 있었는데 https://www.acmicpc.net/board/view/47049
4
1 2 1 1
wrong : 13
correct : 12
1 1 1을 먼저 구매해버리면, 뒤에 하나의 공장에서 구매하는 것이 2번 일어나므로 7 + 2 * 3 = 13이 나오게 된다.
그러나, 1 1을 먼저 구매하고, 뒤이어 1 1 1을 구매하면, 5 + 7 = 12로 최소 비용을 구할 수 있게 된다.
즉, a[i + 1] > a[i + 2] 일 때는 a[i + 1] - a[i + 2]만큼의 차이와 a[i] 중 최솟값을 통해 2개의 공장에서 사는 경우를 먼저 처리해주고,
곧이어 바로 3개의 공장에서 구매할 수 있는 경우를 처리해준다.
(어차피 a[i + 1] - a[i + 2]보다 a[i]가 더 작을 때, a[i]가 0이 되는데 7 * 0 = 0이므로 상관없다.)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #include <bits/stdc++.h> using namespace std; #define Max 10100 int n, a[Max]; int main() { cin.tie(0); scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } int answer = 0; for (int i = 0; i < n; i++) { if (a[i + 1] > a[i + 2]) { int two = min(a[i], a[i + 1] - a[i + 2]); answer += 5 * two; a[i] -= two; a[i + 1] -= two; int three = min(a[i], min(a[i + 1], a[i + 2])); answer += 7 * three; a[i] -= three; a[i + 1] -= three; a[i + 2] -= three; } else { int three = min(a[i], min(a[i + 1], a[i + 2])); answer += 7 * three; a[i] -= three; a[i + 1] -= three; a[i + 2] -= three; int two = min(a[i], a[i + 1]); answer += 5 * two; a[i] -= two; a[i + 1] -= two; } answer += 3 * a[i]; } printf("%d\n", answer); return 0; } | cs |
728x90
반응형
'알고리즘 문제 > BOJ' 카테고리의 다른 글
2261번 가장 가까운 두 점 (0) | 2020.03.11 |
---|---|
12018번 Yonsei TOTO (0) | 2020.03.11 |
1826번 연료 채우기 (0) | 2020.03.10 |
16920번 확장 게임 (0) | 2020.03.10 |
17075번 유물 복원 (0) | 2020.03.09 |