문제

문제 링크

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.

출력

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다.

예제

4
2 3 1
5 2 4 1

나의 접근 방법

연료값이 가장 싼 곳을 계속해서 이용한다고 생각하면 쉽다. 연료를 무제한으로 채울 수 있다고 가정했으니 min값을 기억해뒀다가 새로운 도시의 연료값이 min값보다 싸면 바꿔주고 그렇지 않으면 min값의 연료를 사용하면 된다.

내가 실수했던 것

각 도시간의 거리가 1이상 1000000000 이하, 리터당 가격이 1이상 1000000000 이하인 줄 알고 1000000000 * 1000000000 * 100000이 정답의 범위인 줄 알고 unsigned long long으로도 값을 저장할 수 없다고 판단하고 string을 활용한 덧셈을 구현했다. 그런데 다시 읽어보니 가장 왼쪽부터 오른쪽까지 가는 거리가 1000000000이었다. 즉 long long으로도 커버가 되는 거리인데 왜 내 코드에서는 WA가 났던 것일까 생각해봤더니 각 도시간의 거리와 연료의 가격을 int로 저장하고 있었던 것이 문제였다. unsigned long long * int 의 연산이 발생해서 int로 변환이 되었던 것이다. 앞으론 주의해야겠다.

코드

이왕 string으로 큰 수 더하는 함수를 짜둔 김에 코드를 2개다 공유한다.

// 코드1
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int main(void){
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  int N, min=1000000000;
  cin>>N;
  vector<unsigned long long> dist(N-1), price(N);
  long long result = 0;
  for(int i = 0 ; i<N-1 ; i++) cin>>dist[i];
  for(int i = 0 ; i<N ; i++) cin>>price[i];
  for(int i = 0 ; i<N-1 ; i++){
    min = min > price[i] ? price[i] : min;
    result += min * dist[i];
  }
  cout<<result;
  return 0;
}

// 코드2
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

string addNumByString(string A, string B){
  int sum = 0;
  string result = "";
  while(!A.empty() || !B.empty() || sum){
    if(!A.empty()){
      sum += A.back() - '0';
      A.pop_back();
    }
    if(!B.empty()){
      sum += B.back() - '0';
      B.pop_back();
    }
    result += (sum % 10) + '0';
    sum /= 10;
  }
  reverse(result.begin(), result.end());
  return result;
}

int main(void){
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  int N, min=1000000000;
  cin>>N;
  vector<unsigned long long> dist(N-1), price(N);
  vector<string> sums(N-1);
  long long result = 0;
  for(int i = 0 ; i<N-1 ; i++) cin>>dist[i];
  for(int i = 0 ; i<N ; i++) cin>>price[i];
  for(int i = 0 ; i<N-1 ; i++){
    min = min > price[i] ? price[i] : min;
    unsigned long long sum = min*dist[i];
    sums[i] = to_string(sum);
  }
  string now = sums[0];
  for(int i = 1 ; i<N-1 ; i++) now = addNumByString(now, sums[i]);
  cout<<now;
  return 0;
}