백준 13305 주유소(자바)

https://www.acmicpc.net/problem/13305

13305번: 주유소

 

문제

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다. 

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

입력

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

출력

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

서브태스크

번호배점제한

1	17	모든 주유소의 리터당 가격은 1원이다.
2	41	2 ≤ N ≤ 1,000, 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 최대 10,000, 리터 당 가격은 최대 10,000이다.
3	42	원래의 제약조건 이외에 아무 제약조건이 없다.

 

그리디 단계별 문제에 있는 문제이다.

 

그리디 문제를 파악하려면 종이랑 펜으로 직접 경우를 따져가며 어떤 방법이 있는지 그려보는 방법이 최고라고 생각한다.

 

이 문제를 해결하기 위해 생각했던 방법은 우선 도시의 마지막 리터 가격은 신경을 쓸 필요가 없다는 점이다.

 

그리고 count 위치를 시작으로 이후의 가격이 전부 비싸다면 count위치에서 전부 주유를 하고 가면 최적이 된다.

 

우선 전체 코드를 보자

 

import java.util.Scanner;                                                                     
                                                                                              
public class baek_13305_주유소_실버3 {                                                             
	public static void main(String[] args) {                                                  
		Scanner sc = new Scanner(System.in);                                                  
		int N = sc.nextInt(); // 도시의 개수                                                       
		long[] distance = new long[N-1]; // 도시의 거리                                            
		long[] city = new long[N]; // 도시(마지막은 있으나 마나)                                         
		long sum = 0; // 도시의 길이를 저장할 변수                                                       
		// 거리를 입력 받음                                                                          
		for(int i=0; i<distance.length; i++) {                                                
			distance[i] = sc.nextInt();                                                       
		}                                                                                     
		// 도시의 리터 가격을 입력 받음                                                                   
		for(int i=0; i<city.length; i++) {                                                    
			city[i] = sc.nextInt();                                                           
		}                                                                                     
		                                                                                      
		int count = 0; // 인덱스 번호                                                              
		int temp = 0; // 임시 인덱스 번호                                                            
		boolean flag = true; // 임시 플래그                                                        
		while(true) {                                                                         
			// count부터 도시의 길이까지 for문을 돈다.                                                     
			for(int i=count; i<city.length; i++) {                                            
				if(city[count]>city[i]) { // count도시보다 다음 도시가 크다면                             
					flag = false; // 플래그 false로 바꾸고                                           
					temp = i; // 임시변수에 i 저장                                                   
					for(int j=count; j<temp; j++) { // count부터 temp까지 돌면서                     
						sum += distance[j]*city[count]; // count도시부터 거리를 곱해준다.                
					}                                                                         
					count = i; // 끝나면 count를 i로 바꿔서 도시의 위치를 정해주고                              
					temp = N; // 임시변수를 다시 N으로 바꿔서 도시 끝으로 초기화                                  
					break; // 끝났으니 브레이크                                                       
				}	                                                                          
			}                                                                                 
			// 만약에 flag가 true면 count번째 도시보다 싼 곳이 없다는 소리                                       
			if(flag==true) {                                                                  
				for(int i=count; i<city.length-1; i++) {                                      
					sum+=distance[i]*city[count]; // 거리를 전부 곱해서 더해준다                          
				}                                                                             
				// while문 탈출                                                                  
				break;                                                                        
			}                                                                                 
			// 위 조건을 못돌았으면 flag 다시 true로 초기화                                                  
			flag = true;                                                                      
		}                                                                                     
		System.out.println(sum);                                                              
		                                                                                      
	}                                                                                         
}

코드를 하나씩 살펴보겠다.

 

 

import java.util.Scanner;                                             
                                                                      
public class baek_13305_주유소_실버3 {                                     
	public static void main(String[] args) {                          
		Scanner sc = new Scanner(System.in);                          
		int N = sc.nextInt(); // 도시의 개수                               
		long[] distance = new long[N-1]; // 도시의 거리                    
		long[] city = new long[N]; // 도시(마지막은 있으나 마나)                 
		long sum = 0; // 도시의 길이를 저장할 변수                               
		// 거리를 입력 받음                                                  
		for(int i=0; i<distance.length; i++) {                        
			distance[i] = sc.nextInt();                               
		}                                                             
		// 도시의 리터 가격을 입력 받음                                           
		for(int i=0; i<city.length; i++) {                            
			city[i] = sc.nextInt();                                   
		}                                                             
		                                                              
		int count = 0; // 인덱스 번호                                      
		int temp = 0; // 임시 인덱스 번호                                    
		boolean flag = true; // 임시 플래그

도시의 거리는 N-1로 주어지고 있다.

처음에는 전부 int로 설정을 했지만 서브태스크 3번을 보면

3

42

원래의 제약조건 이외에 아무 제약조건이 없다.

라는 조항이 있다.

문제 조건을 봤을 때 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.

라는 조건이 있는데 전부 더했을 때 int의 한계를 초과하고 stack overflow가 날 경우가 있어서 long으로 설정했다.

(실제로 int로 제출했더니 1,2번의 점수인 58점이 나오고 3번 조건에서는 틀려버린다)

 

거리와 리터 가격을 받은 뒤 내가 출발을 할 도시 번호인 count와

만약에 count부터 쭉 탐색을 했을 때 count보다 싼 도시를 발견하면 그 위치를 저장할 temp 변수를 선언했다.

또 싼 도시를 발견했다는 신호를 주기 위해 flag도 하나 만들었다.

 

 

 

while(true) {                                                                 
	// count부터 도시의 길이까지 for문을 돈다.                                             
	for(int i=count; i<city.length; i++) {                                    
		if(city[count]>city[i]) { // count도시보다 다음 도시가 크다면                     
			flag = false; // 플래그 false로 바꾸고                                   
			temp = i; // 임시변수에 i 저장                                           
			for(int j=count; j<temp; j++) { // count부터 temp까지 돌면서             
				sum += distance[j]*city[count]; // count도시부터 거리를 곱해준다.        
			}                                                                 
			count = i; // 끝나면 count를 i로 바꿔서 도시의 위치를 정해주고                      
			temp = N; // 임시변수를 다시 N으로 바꿔서 도시 끝으로 초기화                          
			break; // 끝났으니 브레이크                                               
		}	                                                                  
	}

우선 while문을 true로 줘서 무한으로 돌게 설정한다.

바로 for문을 도는데 count부터 도시의 길이까지 돌게 만든다.(처음이니깐 count=0)

만약에 count도시보다 뒤에 더 싼 도시를 발견한다면 flag를 false로 만들고 해당 위치를 temp에 저장한다.

그리고 count도시부터 temp이전 도시까지 거리를 곱해주면서 sum에 더해준다.

 

for문이 끝나면 count는 i번째부터 시작하면 되니 i로 설정해주고

temp는 N으로 설정해서 다시 도시 끝까지 탐색할 수 있도록 변경한다.

if문에 걸렸으면 뒤에는 더 for문을 안 돌아도 되므로 break를 걸어버린다.

 

 

			// 만약에 flag가 true면 count번째 도시보다 싼 곳이 없다는 소리                                  
			if(flag==true) {                                                             
				for(int i=count; i<city.length-1; i++) {                                 
					sum+=distance[i]*city[count]; // 거리를 전부 곱해서 더해준다                     
				}                                                                        
				// while문 탈출                                                             
				break;                                                                   
			}                                                                            
			// 위 조건을 못돌았으면 flag 다시 true로 초기화                                             
			flag = true;                                                                 
		}                                                                                
		System.out.println(sum);                                                         
		                                                                                 
	}                                                                                    
}

for문이 끝나고 만약에 flag가 그대로 true면 count번째 도시보다 싼 도시는 없다는 소리이므로

count도시에서 주유를 전부 채워버리면 된다.

만약에 if문을 돌지 않았으면 flag는 false이므로 다시 true로 바꿔주고 while문 처음으로 돌아가게 된다.