[백준] 1257 엄청난 부자 Python 3

문제 설명

먼저 문제를 이해해봅시다. 입력으로는 다음과 같은 값들이 주어집니다:

1. 목표 값 𝑚m
2. 리스트의 길이 𝑛n
3. 𝑛n개의 정수로 이루어진 리스트 𝑎a

우리는 리스트 𝑎a의 요소들을 사용하여 목표 값 𝑚m에 도달하는 가장 빠른 방법을 찾아야 합니다.

코드 설명

다음은 문제를 해결하기 위해 작성한 Python 코드입니다.

import heapq

def main():
    # 입력 받기
    m = int(input())
    n = int(input())
    a = list(map(int, input().split()))

    # 최대 요소 값 구하기
    s = max(a)

    # dp 배열 초기화
    dp = [float('inf')] * s
    dp[0] = 0

    # 우선순위 큐 초기화
    pq = []
    heapq.heappush(pq, (0, 0))

    # 다익스트라 알고리즘 실행
    while pq:
        tdis, tpos = heapq.heappop(pq)
        if dp[tpos] != tdis:
            continue
        for ai in a:
            t = tpos + ai
            new_pos = t % s
            new_dist = tdis + 1 - t // s
            if dp[new_pos] > new_dist:
                dp[new_pos] = new_dist
                heapq.heappush(pq, (new_dist, new_pos))

    # 결과 출력
    print(dp[m % s] + m // s)

if __name__ == "__main__":
    main()

코드 동작 원리

1. 입력 받기: 목표 값 𝑚m, 리스트의 길이 𝑛n, 그리고 리스트 𝑎a를 입력받습니다.
2. 최대 요소 값 구하기: 리스트 𝑎a에서 가장 큰 요소 값을 구하여 변수 𝑠s에 저장합니다.
3. DP 배열 초기화: 크기 𝑠s의 DP 배열을 무한대로 초기화하고, 시작점인 0을 0으로 설정합니다.
4. 우선순위 큐 초기화: 최소 힙을 사용하기 위해 우선순위 큐를 초기화하고, (0, 0)을 추가합니다.
5. 다익스트라 알고리즘 실행: 큐에서 현재 위치와 거리를 꺼내고, 리스트 𝑎a의 요소들을 더하거나 빼서 새로운 위치와 거리를 계산합니다. 이때, 새로운 거리가 기존 거리보다 작으면 DP 배열을 갱신하고, 큐에 추가합니다.
6. 결과 출력: 목표 값 𝑚m에 도달하는 최소 거리를 출력합니다.

다익스트라 알고리즘의 활용

이 문제에서 다익스트라 알고리즘을 사용한 이유는 각 정점(위치)에서 가능한 모든 이동(리스트 𝑎a의 요소를 더하거나 빼기)을 고려하여 최단 거리를 찾기 위해서입니다. 이를 통해 목표 값 𝑚m에 도달하는 가장 빠른 방법을 효율적으로 찾을 수 있습니다.