[백준 28324] 2023 정올 초중고 2차 스케이트 연습

문제 출처 : https://www.acmicpc.net/problem/28324

28324번: 스케이트 연습

이 문제는 2023년 정보올림피아드 2차 대회 초등부 2번, 중등부 1번, 고등부 1번으로 출제된 문제 입니다.

문제를 읽어보면 왠지 DP의 냄새가 나는 문제 입니다. 하지만 잘 생각해보면 굳이 DP를 사용하지 않고도 문제를 해결할 수 있습니다. 그리디로 탐욕적으로 문제를 해결해 보겠습니다.

문제 이해하기

이 문제를 해결하기 위해서 알아야 하는 것은 크게 두가지 입니다.

1. 속력을 올리는 것은 마음대로 할 수 있다.
2. 속력을 줄일 때에는 1씩 줄일 수 있다.

이 두가지중 제약이 되는 사항은 2번인 속력을 1씩 줄일 수 있다는 것 입니다. 아무리 속력의 제한이 크다고 하더라도 마지막 지점은 1 이상이 될 수 없습니다. 왜냐하면 도착 지점은 속력이 0이 되어야 하기 때문 입니다.

마찬가지로 마지막에서 두 번째 지점은 속력이 2 이상이 될 수 없습니다. 그래야 마지막 지점에서 속력이 1이 될 수 있고, 도착지점에서는 0이 될 수 있기 때문 입니다.

이제 마지막에서 세 번째 지점은 속력이 3 이상 될 수 없다는 것을 알 수 있습니다.

마지막에서 네 번째 지점이 몇이 될 수 있을지를 생각해 보겠습니다. 먼저 이전과 같이 4이상의 큰 수라면 이전과 똑같이 4가 될 것입니다. 하지만 이번에는 3일 수도 있습니다. 그럼 똑같이 3으로 유지하면 됩니다. 문제는 갑자기 작아지는 1일 경우를 생각해 보겠습니다. 마지막의 네 번째가 1이라면 문제가 생길까요? 문제가 생길것 같아 보이지만 전혀 문제가 생기지 않습니다. 왜냐하면 속력을 올리는 것에는 제한이 없기 때문 입니다. 1에서 3으로 속력을 올리는 데에는 전혀 문제가 없습니다. 따라서 속력이 1이라면 1로 바꿔주면 그만 입니다.

이렇듯 문제를 거꾸로 생각하면 모든 문제가 쉽게 해결 가능 합니다.

해결 알고리즘

이 문제를 해결하기 위해서는 아래와 같은 알고리즘을 사용하면 됩니다.

1. 뒤에서 부터 현재 속력보다 제한된 속력이 크다면 속력을 1씩 올려줍니다.
2. 현재 속력보다 제한된 속력이 작다면 제한된 속력으로 변경해 줍니다.
3. 현재 속력을 매번 성과에 더해줍니다.

코드 작성

그럼 이 코드를 직접 작성해 보겠습니다.

입력 받기

N = int(input())
V = tuple(map(int, input().split()))

먼저 N개의 지점의 개수 N을 입력 받습니다. 다음으로 제한된 속력의 크기 V를 받습니다. V는 수정이 필요 없기 때문에 튜플로 하였습니다.

속력 구하기

speed = 0
total = 0
for v in V[::-1]:
    if speed < v:
        speed += 1
    else:
        speed = v
        
    total += speed

print(total)

speed는 현재의 속력 입니다. 그리고 total은 최대의 성과이자 구하려는 답 입니다.

먼저 속력 V를 뒤집기 위해서 for 문을 V[::-1]로 탐색 합니다. 이 탐색 방법이 잘 이해 안된다면 아래 리스트 슬라이싱에 대한 글을 확인 바랍니다. 리스트나 튜플이나 슬라이싱에는 차이가 없습니다.

https://wikidocs.net/192334#2-

01. 리스트 기본 사용방법

다음으로 제한된 속력이 현재의 속력보다 크다면 1씩 속력을 증가시켜 줍니다. 그 외에는 제한된 속력으로 바꿔줍니다. 그렇게 정해진 속력 speed를 total 값에 더해주어 성과를 구해줍니다. 그리고 최종적으로 성과를 출력해 주면 됩니다.

전체 코드

그럼 전체 코드를 확인해 보겠습니다.

N = int(input())
V = tuple(map(int, input().split()))

speed = 0
total = 0
for v in V[::-1]:
    if speed < v:
        speed += 1
    else:
        speed = v
        
    total += speed

print(total)