[그리디] 코딩테스트 문제 TIL (주유소) - 백준 13305번

말하는 감자·2024년 11월 28일

TIL algorithm baekjoon greedy python 그리디 백준 알고리즘 코딩테스트 코딩테스트 준비 파이썬

코딩테스트 유형별 풀이

목록 보기

29/67

전 코테 문제를 푸는것을 좋아하지 않습니다. 하지만 어쩌겠어요.. 해야합니다. 오늘 문제입니다!!

1. 오늘의 학습 키워드

Greedy
문제 풀이 센스

문제 풀이 센스라고 적었는데 왜그런지는 문제 풀이를 진행하면서 기록하도록 하겠습니다!

2. 문제: 13305. 주유소

단계: 🥈실버 3단계
알고리즘 분류:
- 그리디 알고리즘
출처: https://www.acmicpc.net/problem/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	원래의 제약조건 이외에 아무 제약조건이 없다.

예제 입력 1 복사

4
2 3 1
5 2 4 1

예제 출력 1 복사

예제 입력 2 복사

4
3 3 4
1 1 1 1

3. 문제 풀이

Step1. 문제 이해 및 분석하기

오늘 문제는 비교적 긴 설명을 포함하고 있지만, 핵심은 간단합니다. N개의 도시가 일직선 상에 위치하고 있으며, 제일 왼쪽 도시에서 제일 오른쪽 도시로 자동차를 이용해 이동해야 합니다.

자동차는 처음에 기름이 없기 때문에 주유소에서 기름을 충전해야 출발할 수 있습니다. 도로를 1km 이동할 때마다 1리터의 기름이 필요하며, 각 도시에 있는 주유소의 기름 가격은 다릅니다. 이 문제는 각 도시의 주유소에서 기름을 충전하며 제일 오른쪽 도시로 이동할 때, 최소 비용으로 목적지에 도달하는 방법을 계산하는 문제입니다.

문제의 주요 조건:

각 도시에 위치한 주유소의 리터당 가격은 다를 수 있습니다.
인접한 두 도시 사이의 도로 길이는 서로 다를 수 있습니다.
기름통의 크기는 무제한으로 가정합니다. 즉, 한 번 충전할 때 필요한 만큼 기름을 넣을 수 있습니다.

문제의 핵심:

최소 비용으로 목적지까지 도달하려면, 가능한 한 가장 저렴한 가격의 주유소에서 최대한 많은 기름을 충전해 이동해야 합니다. 따라서, 현재 위치에서 앞으로 이동할 때 현재 주유소의 가격과 다음 도시들의 주유소 가격을 비교해 충전 전략을 세우는 것이 중요합니다.

이러한 접근 방식은 가장 효율적인 선택을 반복하는 그리디 알고리즘의 대표적인 예입니다.

💡 이렇게 문제를 이해하는 과정에서도 문제 분석 및 코드 설계까지 가능할 수 있습니다. 저도 빨리 센스 및 눈치, 실력이 키워졌으면 좋겠습니다!!

오랜만에 바로 문제의 해결이 보입니다. 이제 입출력과 제약 조건을 살펴보겠습니다.

Input:
- 첫째 줄에는 2이상 $10^5$ 이하의 정수가 주어집니다.
  - 아무래도 이 값이 시간 복잡도에 영향을 줄 것입니다. $10^5$ 이므로 $O(n^2)$ 보다 작은 시간 복잡도로 구현해야 합니다.
- 두번째 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어집니다.
- 마지막 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어집니다.
- 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수입니다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수입니다.
  - 이 값의 크기는 시간 복잡도에 영향을 주지 않습니다.
Output:
- 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 반환합니다.

Step2. 코드 설계

초기화
- 처음 출발할 때는 첫 번째 도시의 기름값을 min_price로 초기화합니다.이는 가장 저렴한 가격을 기준으로 계산을 시작하기 위해 필요합니다.
- 전체 이동 비용을 계산하기 위해 result를 0으로 초기화합니다.
도시 순회 (그리디 접근)
- 도로를 따라 이동하며, 각 도시에서 다음 도시까지의 이동 비용을 계산합니다.
- 현재 도시의 기름값이 min_price보다 작으면, 더 저렴한 기름값을 발견한 것이므로 min_price를 갱신합니다.
  - 이는 앞으로 이동할 구간에서도 최소 비용을 보장하기 위한 그리디 전략입니다.
- min_price를 사용해 현재 도시에서 다음 도시까지 이동하는 비용을 계산하고, result에 누적합니다.
결과 반환
- 마지막 도시까지 이동 비용을 모두 계산한 후, 누적된 최소 비용 result를 반환합니다.

Step3. 코드 구현

import sys

# 입력 처리
N = int(sys.stdin.readline().strip())  # 도시의 수
distance = list(map(int, sys.stdin.readline().split()))  # 도로 길이
price = list(map(int, sys.stdin.readline().split()))     # 각 도시의 주유소 가격

def sol(N, distance, price):
    # 초기화
    min_price = price[0]  # 첫 번째 도시의 기름값을 기준으로 초기화
    result = 0            # 누적 비용 계산용 변수
    
    # N-1번 순회 (마지막 도시는 이동하지 않음)
    for i in range(N-1):
        # 더 저렴한 기름값 발견 시 갱신
        if min_price > price[i]:
            min_price = price[i]
        
        # 현재 구간의 최소 비용 계산
        result += min_price * distance[i]
    
    # 누적된 최소 비용 반환
    return result

# 결과 출력
print(sol(N=N, distance=distance, price=price))

코드 설명:

입력 처리
- 첫 번째 입력값은 도시의 개수 N입니다.
- 두 번째 줄은 distance 리스트로, 각 도로의 길이를 나타냅니다.
- 세 번째 줄은 price 리스트로, 각 도시의 주유소 기름값을 나타냅니다.
초기화 및 순회
- min_price를 첫 번째 도시의 기름값으로 초기화합니다.
- 도로를 따라 N-1번 순회하며 다음을 수행합니다:
  1. 현재 도시의 기름값이 min_price보다 작으면 갱신합니다.
  2. min_price를 기준으로 다음 도로 구간의 이동 비용을 계산해 result에 누적합니다.
결과 반환 및 출력
- 모든 도시를 순회한 후, 최소 비용 result를 출력합니다.

시간 복잡도:

초기화: $O(1)$
순회: $O(N-1)$
- 각 도로와 도시를 한 번씩 순회하며 계산합니다.
최종 복잡도: $O(N)$
- 입력 크기가 최대 100,000이므로 제한 조건을 만족합니다.

결과:

4. 마무리

이번 문제는 문제 풀이 센스가 중요한 문제였습니다. 문제를 읽으면서 바로 최적화 방법이 떠오르지 않았다면, 여러 시뮬레이션을 통해 규칙을 찾아야 했을 것입니다. 하지만 도로를 순회하며 최소 기름값만 고려하면 된다는 직관이 그리디 알고리즘의 핵심 포인트를 잡게 해줬습니다.

앞으로도 그리디 문제를 풀 때는 매 순간 최적의 선택을 통해 전체 최적화를 달성할 수 있는지 고민하는 연습을 해야겠습니다.