주유소 << 문제 클릭!
✅문제 설명
- 입력
: 도시의 개수 정수 N (2 <= N <= 100,000)
: 두 도시를 연결하는 도로의 길이 N-1개, 자연수, 단위(km),
이때 제일 왼쪽 도시부터 제일 오른쪽까지 도시의 거리는 1이상 1,000,000,000 이하 자연수 즉, 거리가 0인 경우도 있을 듯
: 리터당 가격, N개의 자연수, 1이상 1,000,000,000 이하의 자연수
- 출력
: 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용
❗핵심원리
- Greedy Algorithm 참고자료
: 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만 쫓는 것.
: 그 순간에 대해 지역적으로 최적이지만 최종적인 선택에서는 최적이라는 보장이 없다!
=> 따라서 그리디 알고리즘을 적용하려면 지역적으로 최적이면서 전역적으로 최적인 문제!!
: 앞의 선택이 이후의 선택에 영향을 주치 않아야 하며 부분 문제에 대한 최적해는 전체 문제에 대한 최적해가 되어야 한다.
- 원리
: 먼저 맨 처음 주유소에서 모든 거리를 커버하는 경우의 가격을 배열에 담는다.
: 주유소를 하나씩 추가해서 min(기존 배열에 있던 가격, 새롭게 주유소를 추가했을 때 가격)을 비교해서 작은 값으로 update 한다.
✅ 주유소를 하나씩 추가하면서 해당 주요소 가격X거리에 해당하는 금액을 update하는 방식
💻코드
1차
- 새롭게 주유소가 추가 되면 기존의 주요소 가격과 새로운 주요소 가격을 비교한 후 업데이트 하는 방식
#include <iostream>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int N = 0; // 주유소 개수
cin >> N;
int* d = new int[N - 1]; // 거리 저장
int* total = new int[N - 1]; // 최종 금액
for (int i = 0; i < N - 1; i++) {
cin >> d[i]; // 값 저장
}
//초기화
int temp = 0; // 임시 주요소 금액
int num = 0; // 최소 주요소 금액
cin >> temp; // 처음 주요소 가격 받기
total[0] = temp * d[0]; // 금액 저장
num = d[0]; // 해당 주요소 저장
for (int i = 1; i < N - 1; i++) {
cin >> temp;
if (num * d[i] > temp * d[i]) { // 새로 upate된 주유소가 더 값이 적으면
total[i] = total[i - 1] + temp * d[i]; // 업데이트
num = temp; // 주요소도 바꾸기
}
else {
total[i] = total[i - 1] + num * d[i];
}
}
cout << total[N - 2]; // 마지막 금액
delete[] d; // 할당 해제
delete[] total;
}
✅ 문제 원인
- 굳이 배열로 저장해서 비교? 추가되는 값만 비교해도 되니까 total[]을 sum으로 두자.
- num에 현재 주요소의 가격을 저장해야 했는데 거리를 저장했음
2차
#include <iostream>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int N = 0; // 주유소 개수
cin >> N;
int* d = new int[N - 1]; // 거리 저장
int sum = 0;
for (int i = 0; i < N - 1; i++) {
cin >> d[i]; // 값 저장
}
//초기화
int temp = 0; // 임시 주요소 금액
int num = 0; // 최소 주요소 금액
cin >> temp; // 처음 주요소 가격 받기
sum += temp * d[0]; // 금액 저장
num = temp; // 해당 주요소 저장
for (int i = 1; i < N - 1; i++) {
cin >> temp;
if (num * d[i] > temp * d[i]) { // 새로 upate된 주유소가 더 값이 적으면
sum += temp * d[i]; // 업데이트
num = temp; // 주요소도 바꾸기
}
else {
sum += num * d[i];
}
}
cout << sum; // 마지막 금액
delete[] d; // 할당 해제
}
✅ 문제 원인
- sum의 type이 int라서, long long으로 바꿈 (리터와 가격의 범위가 1억이므로 바꿔야 함) -> 바꿔도 오류남
- 그래서 모든 type 애들을 long long으로 바꿈 -> 왜 되는 걸까?
3차
#include <iostream>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
long long int N = 0; // 주유소 개수
cin >> N;
long long int* d = new long long int[N - 1]; // 거리 저장
long long sum = 0;
for (int i = 0; i < N - 1; i++) {
cin >> d[i]; // 값 저장
}
//초기화
long long int temp = 0; // 임시 주요소 금액
long long int num = 0; // 최소 주요소 금액
cin >> temp; // 처음 주요소 가격 받기
sum += temp * d[0]; // 금액 저장
num = temp; // 해당 주요소 저장
for (int i = 1; i < N - 1; i++) {
cin >> temp;
if (num * d[i] > temp * d[i]) { // 새로 upate된 주유소가 더 값이 적으면
sum += temp * d[i]; // 업데이트
num = temp; // 주요소도 바꾸기
}
else {
sum += num * d[i];
}
}
cout << sum; // 마지막 금액
delete[] d; // 할당 해제
}
- 형변환 문제 참고자료
long long 타입인 sum에 int의 값을 할당해서 에러가 난게 아닐까? 라는 추측을 했는데....
알고 스터디 선배의 말에 따르면..
4바이트(int)랑 4바이트(int) 곱셈 연산하는 과정에서 오버플로우가 발생!
즉,형변환 전에 오버플로우가 난다는 것이다!(처 초록색 밑줄이 보이는가?)
이렇게 int X int 곱이 21억을 넘어갈 것 같으면 long long X int 로 바꾸면 오버플로우가 안 뜬다.
SW Engineer 꿈나무 / 자의식이 있는 컴퓨터