13305_주유소 (구현이;;)

사용 알고리즘: 그리디

사용 언어: java

 

package week33;

import java.util.*;
public class Main_bj_13305_주유소 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] length = new long[n-1];
		long[] cost = new long[n];
		
		for (int i = 0; i < n-1; i++) {
			length[i] = sc.nextInt();
		}
		for (int i = 0; i < n; i++) {
			cost[i] = sc.nextInt();
		}
		
		long answer = 0; //답
		long minCost = cost[0];
		
		for (int i = 0; i < n-1; i++) {
			if(minCost > cost[i]) 
				minCost = cost[i];
			
			answer += minCost * length[i];
		}
		
		System.out.println(answer);
	}

}

 

앞으로 남아있는 거리에서 

지금이 제일 적은 cost이면: 남은 거리는 여기서 다 채우고 가면 됨

그렇지 않다면: 나보다 적은 cost가 나올 때까지는 여기서 채우고 가면 됨

 

이라는 그리디 문제인데...

 

for문 구현이 어려웠음;ㅎㅎㅎ...

나는 minCost를 갱신하지 못할 때는 

accumualtedLength라는 변수에 움직일 거리를 계속 누적했는데

이럴 필요 없이 

그때 그때 가장 작은 애를 곱해서 더해주면 복잡하지 않게 계산할 수 있었다..

 

참고로, 논리가 틀리지 않았는데 부분점수가 나온다? -> 변수형을 잘 생각해보기