[백준] 28324번 스케이트 연습

park geonwoo·2024년 11월 19일
코딩테스트

코딩테스트

목록 보기
31/32

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

이번 문제는 스케이트 코스에서 각 중간 지점의 속도 제한을 고려하여, 스케이터가 이동해야 하는 경로의 속도 합을 최대화하는 문제입니다. 효율적인 속도 할당을 통해 전체 이동 거리의 합을 최대화하면서도 주어진 속도 제한과 속도 조절 규칙을 준수해야 합니다.

문제 이해

문제 요약

  • 목표:
    • 시작 지점에서 출발하여 번호가 증가하는 순서대로 1번부터 N번 중간 지점을 방문하고, 최종적으로 M번 집에 도착할 때까지 이동하면서, 각 중간 지점에서의 속력의 합을 최대화하는 것.
  • 이동 규칙:
    • 출발 지점: 속력 0에서 출발.
    • 각 중간 지점:
      • 속력 제한 V_i가 있음.
      • 속력을 높일 때는 원하는 만큼 높일 수 있음.
      • 속력을 낮출 때는 마지막으로 방문했던 지점에서의 속력에서 1만큼만 낮출 수 있음.
      • 속력을 변경하지 않고 유지하는 것도 가능.
      • 속력은 0이 될 수 없음 (출발 및 도착 지점을 제외).
    • 도착 지점: 속력 0으로 도착.
  • 입력:
    • 첫 번째 줄: 중간 지점의 수 N (1 ≤ N ≤ 500,000)과 도착 지점 번호 M (3 ≤ M ≤ 10^9).
    • 다음 N줄: 각 중간 지점의 속도 제한 V_i (1 ≤ V_i ≤ 1,000,000,000).
  • 출력:
    • 스케이터가 이동하는 동안 방문한 각 중간 지점에서의 속력 합의 최대값.

예제 분석

예제 입력 1:

3
2 3 1

예제 출력 1:

5

해석:

  • 중간 지점 1: 속력 2
  • 중간 지점 2: 속력 2
  • 중간 지점 3: 속력 1
  • 속력의 합: 2 + 2 + 1 = 5

예제 입력 2:

4
23 7 1 5

예제 출력 2:

7

해석:

  • 중간 지점 1: 속력 3
  • 중간 지점 2: 속력 2
  • 중간 지점 3: 속력 1
  • 중간 지점 4: 속력 1
  • 속력의 합: 3 + 2 + 1 + 1 = 7

해결 방법

접근 방식

스케이터의 속도를 최대화하기 위해 뒤에서부터 앞으로 속도를 할당하는 그리디 알고리즘을 사용합니다. 이를 통해 각 중간 지점에서 가능한 최대 속도를 결정하면서도, 속도를 낮출 때의 제한 사항을 만족시킬 수 있습니다.

  1. 뒤에서부터 속도 할당:
    • 스케이터는 마지막 중간 지점에서 도착 지점으로 가야 하므로, 마지막 중간 지점의 속도는 최소 1이어야 합니다.
    • 이전 중간 지점(뒤쪽)에서는 현재 중간 지점의 속도보다 최대 1만큼 높을 수 있습니다.
    • 각 중간 지점의 속도는 그 지점의 속도 제한 V_i를 초과할 수 없으며, 다음 지점의 속도보다 최대 1만큼 높을 수 있습니다.
  2. 속도 할당 규칙:
    • 마지막 중간 지점에서의 속도 speed[N] = min(V[N], 1) (도착 지점으로 가기 위해 최소 1).
    • 그 이전 중간 지점 i = N-1부터 1까지:
      • speed[i] = min(V[i], speed[i+1] + 1)
  3. 속도 합 계산:
    • 모든 중간 지점에서의 속도를 합산하여 최종 결과를 도출합니다.

알고리즘 단계

  1. 입력 처리:
    • N과 M을 입력받습니다.
    • 각 중간 지점의 속도 제한 V_i를 리스트에 저장합니다.
  2. 뒤에서부터 속도 할당:
    • 마지막 중간 지점의 속도를 min(V[N-1], 1)로 설정합니다.
    • i = N-2부터 0까지 반복하며:
      • speed[i] = min(V[i], speed[i+1] + 1)
  3. 속도 합 계산:
    • 모든 중간 지점에서 할당된 속도를 합산합니다.
  4. 결과 출력:
    • 합산된 속도 값을 출력합니다.

예제 적용

예제 입력 1:

3
2 3 1

속도 할당 과정:

  • 중간 지점 3: speed[2] = min(1, 1) = 1
  • 중간 지점 2: speed[1] = min(3, 1 + 1) = 2
  • 중간 지점 1: speed[0] = min(2, 2 + 1) = 2
  • 속도 합: 2 + 2 + 1 = 5

예제 입력 2:

4
23 7 1 5

속도 할당 과정:

  • 중간 지점 4: speed[3] = min(5, 1) = 1
  • 중간 지점 3: speed[2] = min(1, 1 + 1) = 1
  • 중간 지점 2: speed[1] = min(7, 1 + 1) = 2
  • 중간 지점 1: speed[0] = min(23, 2 + 1) = 3
  • 속도 합: 3 + 2 + 1 + 1 = 7

코드 구현

아래는 위의 접근 방식을 바탕으로 작성한 파이썬 코드입니다. 효율적인 입력 처리를 위해 sys.stdin을 사용하였으며, 시간 및 공간 복잡도를 고려하여 최적화하였습니다.

import sys

def solution():
    import sys
    def input():
        return sys.stdin.read()

    data = input().split()
    idx = 0
    N = int(data[idx])
    idx +=1
    V = list(map(int, data[idx:idx+N]))
    idx +=N

    total =0
    # Initialize the speed at the last intermediate point
    current_speed = min(V[-1], 1)
    total += current_speed

    # Iterate from second last to first
    for i in range(N-2, -1, -1):
        # The maximum speed at this point is min(V[i], current_speed +1)
        current_speed = min(V[i], current_speed +1)
        total += current_speed

    print(total)

if __name__ == "__main__":
    solution()

코드 설명

1. 입력 처리 및 초기화

import sys

def solution():
    import sys
    def input():
        return sys.stdin.read()

    data = input().split()
    idx = 0
    N = int(data[idx])
    idx +=1
    V = list(map(int, data[idx:idx+N]))
    idx +=N
  • sys.stdin.read():
    • 입력을 한 번에 읽어들여 효율적으로 처리합니다.
    • 특히 N이 최대 500,000까지 커질 수 있으므로, 빠른 입력 처리가 중요합니다.
  • data 리스트:
    • 입력을 공백 기준으로 분할하여 리스트에 저장합니다.
    • idx를 사용하여 현재 읽고 있는 위치를 추적합니다.
  • V 리스트:
    • 중간 지점의 속도 제한을 저장하는 리스트입니다.
    • V[0]부터 V[N-1]까지 저장됩니다.

2. 뒤에서부터 속도 할당 및 합산

    total =0
    # Initialize the speed at the last intermediate point
    current_speed = min(V[-1], 1)
    total += current_speed

    # Iterate from second last to first
    for i in range(N-2, -1, -1):
        # The maximum speed at this point is min(V[i], current_speed +1)
        current_speed = min(V[i], current_speed +1)
        total += current_speed
  • current_speed:
    • 현재 할당할 속도를 나타내는 변수입니다.
    • 마지막 중간 지점부터 시작하여, 앞쪽 지점으로 이동하면서 속도를 할당합니다.
  • 속도 할당 규칙:
    • speed[i] = min(V[i], speed[i+1] + 1)
    • 이는 각 중간 지점에서 가능한 최대 속도를 할당하되, 다음 지점의 속도보다 최대 1만큼만 높일 수 있음을 의미합니다.
  • 속도 합산:
    • 각 중간 지점에서 할당된 속도를 total에 더합니다.
    • 이를 통해 최종적으로 속도 합의 최대값을 계산합니다.

3. 결과 출력

    print(total)
  • 최종적으로 계산된 속도 합을 출력합니다.

시간 복잡도 및 효율성

시간 복잡도

  1. 입력 처리:
    • O(N) 시간 복잡도.
    • N개의 속도 제한을 읽어들이고, 리스트에 저장합니다.
  2. 뒤에서부터 속도 할당 및 합산:
    • O(N) 시간 복잡도.
    • 각 중간 지점을 한 번씩 순회하며, 속도를 할당하고 합산합니다.

전체 시간 복잡도: O(N)

  • N이 최대 500,000이므로, 이 알고리즘은 매우 효율적이며 제한 시간 내에 충분히 동작합니다.

공간 복잡도

  1. 입력 저장:
    • O(N) 공간 복잡도.
    • 중간 지점의 속도 제한을 저장하는 리스트 V가 필요합니다.
  2. 기타 변수:
    • O(1) 공간 복잡도.
    • total과 current_speed 변수만을 사용합니다.

전체 공간 복잡도: O(N)

  • N이 최대 500,000으로, 이는 파이썬 리스트에 충분히 저장 가능합니다.

알고리즘 및 자료구조 설명

알고리즘: 그리디 알고리즘을 이용한 뒤에서부터의 속도 할당

  • 그리디 선택:
    • 각 중간 지점에서 가능한 최대 속도를 할당하여 전체 합을 최대화합니다.
    • 뒤에서부터 속도를 할당함으로써, 속도 감소의 제한을 자연스럽게 만족시킵니다.
  • 뒤에서부터 할당 이유:
    • 마지막 중간 지점에서의 속도는 반드시 1이어야 하므로, 이 지점부터 시작하여 앞쪽 지점의 속도를 결정합니다.
    • 각 지점에서 가능한 최대 속도를 할당하면서도, 다음 지점과의 속도 차이를 1 이하로 유지합니다.
  • 속도 할당 규칙:
    • speed[i] = min(V[i], speed[i+1] + 1)
    • 이는 현재 지점에서 가능한 최대 속도를 할당하되, 다음 지점의 속도보다 1만큼만 높일 수 있음을 보장합니다.

자료구조: 리스트(List)

  • V 리스트:
    • 각 중간 지점의 속도 제한을 저장합니다.
    • 인덱스를 통해 각 지점을 효율적으로 접근할 수 있습니다.
  • 변수:
    • total: 전체 속도 합을 저장하는 변수로, 간단한 누적 합산을 위해 사용됩니다.
    • current_speed: 현재 할당할 속도를 추적하는 변수로, 속도 할당 규칙을 적용하는 데 사용됩니다.
profile
park geonwoo
이전 포스트

[프로그래머스] 스킬트리

다음 포스트

[백준] 16493번 최대 페이지 수

0개의 댓글