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 |
Tags
- 18249
- mysqld.sock
- SWEA
- 백준
- 자료구조 목차
- 걷는건귀찮아
- 영상 프레임 추출
- 3344
- 알고리즘
- 유니티
- 2020 KAKAO BLIND RECRUITMENT
- 토글 그룹
- 알고리즘 목차
- c#
- MySQL
- 탄막 이동
- 강의실2
- 수 만들기
- 원형
- 문자열 압축
- 윈도우
- 단어 수학
- 탄막
- 그리디알고리즘
- 회의실 배정
- 3273
- 우분투
- AI Hub
- 탄막 스킬 범위
- 마우스 따라다니기
Archives
- Today
- Total
와이유스토리
[그리디] 백준 18185, 18186 라면 사기 (Small) (Large) C++ 본문
https://www.acmicpc.net/problem/18185
18185번: 라면 사기 (Small)
라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i
www.acmicpc.net
v[i+1] > v[i+2]이면 v[i+1]을 5원으로 먼저 사기(나중에 3원, 3원 사는 것보다 적은 금액으로 살 수 있다)
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<int> v(n+2, 0);
for(int i=0; i<n; i++) cin >> v[i];
int answer = 0;
int cnt = 0;
for(int i=0; i<n; i++) {
if (v[i+1] > v[i+2]) { // v[i+2]를 먼저 구매하면 다음 연속 끊김
cnt = min(v[i], v[i+1] - v[i+2]); // v[i+2]는 다음에 구매 가능
answer += cnt * 5;
v[i] -= cnt;
v[i+1] -= cnt;
cnt = min(v[i], min(v[i+1], v[i+2]));
answer += cnt * 7;
v[i] -= cnt;
v[i+1] -= cnt;
v[i+2] -= cnt;
}
else {
cnt = min(v[i], min(v[i+1], v[i+2]));
answer += cnt * 7;
v[i] -= cnt;
v[i+1] -= cnt;
v[i+2] -= cnt;
cnt = min(v[i], v[i+1]);
answer += cnt * 5;
v[i] -= cnt;
v[i+1] -= cnt;
}
answer += v[i] * 3;
}
cout << answer;
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
long long n, b, c;
cin >> n >> b >> c;
vector<int> v(n+2, 0);
for(int i=0; i<n; i++) cin >> v[i];
long long answer = 0;
long long cnt = 0;
if (b < c) { // 종료
for(int i=0; i<n; i++) answer += v[i];
cout << answer * b;
return 0;
}
for(int i=0; i<n; i++) {
if (v[i+1] > v[i+2]) { // v[i+2]를 먼저 구매하면 다음 연속 끊김
cnt = min(v[i], v[i+1] - v[i+2]); // v[i+2]는 다음에 구매 가능
answer += cnt * (b + c);
v[i] -= cnt;
v[i+1] -= cnt;
cnt = min(v[i], min(v[i+1], v[i+2]));
answer += cnt * (b + 2 * c);
v[i] -= cnt;
v[i+1] -= cnt;
v[i+2] -= cnt;
}
else {
cnt = min(v[i], min(v[i+1], v[i+2]));
answer += cnt * (b + 2 * c);
v[i] -= cnt;
v[i+1] -= cnt;
v[i+2] -= cnt;
cnt = min(v[i], v[i+1]);
answer += cnt * (b + c);
v[i] -= cnt;
v[i+1] -= cnt;
}
answer += v[i] * b;
}
cout << answer;
return 0;
}
'코딩테스트 > 그리디|힙' 카테고리의 다른 글
[그리디] 백준 8980 택배 C++ (0) | 2023.09.27 |
---|---|
[그리디] 백준 1715 카드 정렬하기 C++ (0) | 2023.09.27 |
[그리디] 프로그래머스 [1차] 셔틀버스 C++ (0) | 2023.03.22 |
[그리디] 백준 2839 설탕 배달 C++ (0) | 2022.02.09 |
[그리디] 백준 1931번 회의실 배정 C++ (0) | 2022.01.19 |