티스토리 뷰
728x90
C++ 그리디 알고리즘
좀 쉬어가려고 그리디 풀었는데 그리디 무려 5개월만에 풀어서 좀 낯설었다.
접근방법
지금까지의 최저가를 갖고 가다가 그 최저가 보다 더 적은 값을 만나면
거기까지는 지금까지의 최저가로 주유해서 간 다음 그 이후부턴 그 주유소에서 주유하는 식
오답노트
거리랑 금액이 모두 최대가 int최대범위여서
total금액과 중간중간 거리를 더하는 변수는 long long 타입을 써줘야한다.
소스코드
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
int dist[n-1];
for(int i = 0 ; i < n-1 ; i++){
cin >> dist[i];
}
int price[n];
for(int i = 0 ; i < n ; i++){
cin >> price[i];
}
int minPrice = price[0];
int minIndex = 0;
long long totalPrice = 0;
for(int i = 0 ; i < n ; i++){
if(price[i] < minPrice || i == n-1){
long long sumOfdist = 0;
for(int j = minIndex ; j < i ; j++){
sumOfdist += dist[j];
}
totalPrice += sumOfdist*minPrice;
minPrice = price[i];
minIndex = i;
}
}
cout << totalPrice;
return 0;
}
728x90
'알고리즘 문제풀이' 카테고리의 다른 글
[백준 1475] 알고리즘 93일차 : 방 번호 (2) | 2021.02.26 |
---|---|
[백준 1158] 알고리즘 92일차 : 요세푸스 문제 (0) | 2021.02.25 |
[백준 1753] 알고리즘 90일차 : 최단경로 (0) | 2021.02.23 |
[백준 1707] 알고리즘 89일차 : 이분 그래프 (0) | 2021.02.22 |
[백준 7562] 알고리즘 88일차 : 나이트의 이동 (0) | 2021.02.19 |
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 트리
- 최대힙
- 토마토
- 그리디알고리즘
- 브루트포스
- 최단경로
- 프로그래머스
- 가장 큰 수 Swift
- Swift
- 백트래킹
- 게임이론
- 수학
- 이분탐색
- 웹크롤링
- 최소힙
- 스택
- 우선순위큐
- 동적계획법
- 백준
- 다이나믹프로그래밍
- dp
- 정렬
- c++
- BFS
- dfs
- 자바
- 투포인터
- 가장 큰 수 프로그래머스
- 알고리즘
- 파이썬
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함