[Baekjoon] 28324번 : 스케이트 연습

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

28324번: 스케이트 연습

 

문제

여러분은 주어진 스케이트 코스에서 스케이트를 연습하려고 한다. 이 코스는 시작 지점, N개의 중간 지점, 그리고 도착 지점으로 구성 ㅋ어 있다. 이 연습은 시작 지점에서 0의 속력으로 출발하여, 1번 중간 지점부터 N번 중간 지점까지 번호가 증가하는 순서대로 방문하고, 0의 속력으로 도착 지점에 도달한 이후 종료된다.

각 중간 지점에는 속력 제한 Vi가 있어, 다음으로 방문할 지점의 속력 제한을 초과하지 않도록 이동하는 사이에 속력을 조절해야 한다. 속력을 높일 때는 원하는 만큼 높일 수 있지만, 속력을 낮추는 경우에는 마지막으로 방문했던 지점에서의 속력에서 1만큼만 낮출 수 있다. 단, 출발 지점과 도착 지점을 제외한 위치에서 속력은 0이 될 수 없다. 속력을 변경하지 않고 그대로 유지하는 것도 가능하다.

연습의 성과는 각 지점에서의 속력의 합과 같으므로 여러분은 이를 최대화하려고 한다. 스케이트 코스의 속력 제한이 주어졌을 때, 그 코스에서 얻을 수 있는 최대 연습의 성과를 구해보자.

예를 들어, 중간 지점이 3개인 코스의 속력 제한이 V = [2, 3, 1]로 주어진 경우, 2번 중간 지점에서 3의 속력을 유지한다면 3번 중간 지점에서 1이하의 속력이 되도록 조절하는 것이 불가능하다. 이 코스에서 가능한 연습 방법 중 하나로, [2, 2, 1]의 순서대로 속력을 조절한다면 속력의 합은 2 + 2 + 1인 5가 된다. 다른 가능한 연습 방법으로 [1, 1, 1]과 [1, 2, 1]이 있지만, 이들의 속력의 합은 5를 초과하지 않는다. 따라서 이 코스에서 얻을 수 있는 가장 큰 연습의 성과는 5이다.

입력

첫 번째 줄에 N이 주어진다.
두 번째 줄에 V1, V2, ... , VN이 공백을 사이에 두고 차례대로 주어진다.

 

출력

첫 번째 줄에 답을 출력한다.

 

---

소스코드

import java.io.*;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int arr[] = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        long result = 1;
        int pre = 1;
        for (int i = n-2; i >= 0; i--) {
            if(pre < arr[i]) {
                pre++;
            } else if(pre > arr[i]){
                pre = arr[i];
            }
            result += pre;
        }

        System.out.println(result);
    }
}

 

해결 방법

1. 속력을 입력받아 배열에 저장한다.
2. 맨 뒤부터 탐색을 진행한다. 
3. 현재 속력이 이전 속력보다 빠르다면 pre++, 느리다면 pre = arr[i] 연산을 진행한다.
4. 탐색마다 result에 pre값을 더해준다.