[백준 28324번] 스케이트 연습 (C++)

문제링크 : https://www.acmicpc.net/problem/28324

28324번: 스케이트 연습

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll arr[500002];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    ll N;
    cin >> N;

    for(int i=1; i<=N; i++)
    {
        cin >> arr[i];
    }

    ll sum = 0, tmp = 0;

    for(int i=N; i>=1; i--) //뒤에서부터 체크
    {
        tmp = min(tmp+1, arr[i]); //1씩 증가가 가능하다면 1씩 증가가 불가능하다면 현재 배열값을 저장 (2이상으로 감소되는 경우 방지)
        sum+=tmp;
    }

    cout << sum;

    return 0;
}

처음에 앞에서 큰 값부터 시작하여 감소하는 방식으로 생각했다가 시간을 꽤 소모한 문제이다.

뒤에서부터 접근해서 1씩 증가가 가능한지 아닌지로 쉽게 풀이가 가능하다.

(맨 뒤는 무조건 1이기에)

 

맨 뒤부터 시작해서 맨 뒤는 무조건 1이기에 우선 1을 저장하고 더해준다.

이후에 1씩 증가가 가능한지 아닌지 체크하여 1씩 증가가 불가능하다면 현재 배열값을 저장한다.

아래 예시를 보자

<23 7 1 5>

tmp = 0;
5 1 7 23

i = 4, arr[i] = 5 : tmp = 1, sum = 1
i = 3, arr[i] = 1 : tmp = 1(증가 불가), sum = 2
i = 2, arr[i] = 7 : tmp = 2, sum = 4
i = 1, arr[i] = 23 : tmp  =3, sum = 7

뒤에서부터 접근하면 i=3의 경우 처럼 2이상으로 감소되는 경우에 대해 방지가 쉬운데

앞에서부터 접근하며 가장 큰 값을 두고 하나씩 감소시켰다가 2이상으로 감소되는 경우에 대해 어떻게 예외처리해야하는지 헤메면서 시간을 제법 날렸다.

 

위코드는 마찬가지로 tmp를 증가시켜주면서 경우에 따라 tmp를 더할지 arr[i]를 더할지 if문으로 풀었다가 다른 사람의 코드를 보고 훨씬 간결한 풀이를 봐서 참고한 코드이다.