[Java] 백준 13305 주유소

13305 주유소 문제 링크

package forStudy;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_13305 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] len = new int[N-1];
		int[] node = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N-1; i++) {
			len[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			node[i] = Integer.parseInt(st.nextToken());
		}
		// min 기름값 저장
		int priceMin = Integer.MAX_VALUE;
		
		// 0 도시에서 0-1 거리만큼 기름 넣기 (반복)
		int result = 0;
		for(int i =0; i<N-1; i++) {
			priceMin = Math.min(priceMin, node[i]);
			result += (priceMin*len[i]);
		}
		
		System.out.println(result);
	}
}

• O(n)
• 해당 노드까지 가장 적었던 기름값을 저장
• 다음 노드로 이동하면서 이동 거리*가장 적은 기름 값을 result에 더해줌
• 답은 맞음. 근데 점수가 부족.

• 점수 표가 있었네..

#2

package forStudy;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_13305 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] len = new int[N-1];
		int[] node = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N-1; i++) {
			len[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			node[i] = Integer.parseInt(st.nextToken());
		}
		// min 기름값 저장
		int priceMin = Integer.MAX_VALUE;
		
		// 0 도시에서 0-1 거리만큼 기름 넣기 (반복)
		long result = 0L;
		for(int i =0; i<N-1; i++) {
			priceMin = Math.min(priceMin, node[i]);
			result += priceMin*len[i];
		}
		
		System.out.println(result);
	}
}

• 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수
• 지금 범위가 너무 커서 int 범위를 벗어남
• result 자료형을 long으로 바꿔줬는데 안 됨

#3

package forStudy;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_13305 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] len = new int[N-1];
		int[] node = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N-1; i++) {
			len[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			node[i] = Integer.parseInt(st.nextToken());
		}
		// min 기름값 저장
		int priceMin = Integer.MAX_VALUE;
		
		// 0 도시에서 0-1 거리만큼 기름 넣기 (반복)
		long result = 0L;
		for(int i =0; i<N-1; i++) {
			priceMin = Math.min(priceMin, node[i]);
			result += (long) priceMin*len[i];
		}
		
		System.out.println(result);
	}
}

• int를 long에 넣으면 자동으로 형변환 해주는 건 맞음
  
  
• 근데 지금 result += priceMin*len[i];에서는 priceMin*len[i]를 먼저 해주고 result에 대입함
• 따라서 priceMin*len[i]하는 과정에서 이미 int형 범위를 넘어갔기 때문에 값이 변조됨
• 따라서 잘못된 값이 result에 들어감
  
  
• (long) priceMin*len[i]으로 변경하면
• long변수에 int변수를 곱하는 방식이기 때문에 계산 과정에서 int형 변수가 long형으로 자동 형변환됨
• 따라서 곱하는 두 변수 중 하나만 (lnog)으로 명시적 형변환 해주면 값의 변조없이 result에 넣을 수 있음