[BOJ][실4][2847] 게임을 만든 동준이

문제 링크

문제링크

첫 번째 풀이 : 그리디

알고리즘

점수를 감소하는 연산만 할 수 있습니다.

입력받은 숫자가 a,b,c,d,e라면 d는 e-1이 될 때까지 감소해야합니다.
e-4, e-3, e-2, e-1, e가 될때까지 감소하지 않아도 됩니다.

ans += d - (e-1)
d = e-1

위의 과정을 d~a까지 반복합니다.

정답코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int MAX = 1010;

int n, m, k;
int arr[MAX];
int dest[MAX];
int ans = 0;
int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  
  for (int i = n - 2; i >= 0; i--) {
    if (arr[i] < arr[i + 1]) continue;
    ans += arr[i] - (arr[i + 1] - 1);
    arr[i] = arr[i + 1] - 1;
  }
  cout << ans;
  return 0;
}

Success Notice: 수고하셨습니다.