https://www.acmicpc.net/problem/2847
2847, 게임을 만든 동준이
이번 문제는 뒤에서 부터 계산해 나가면 어렵지 않게 풀 수 있는 문제이다.
N의 범위가 1 - 100 이고, 점수는 최대 20,000 점이기 때문에 모든 점수를 합해도 int 범위이기 때문에 int 를 사용해 주었다.
# Process
main
: 차례대로 모든 수를 계산하려면 복잡하기 때문에 뒤에서 부터 계산을 진행했다.
N 번째 요소와 N-1 번째 요소를 비교하여 N-1 번째 요소가 더 크다면 N에서 -1 만큼 해준 수로 값을 변환해주고 그 차이만큼 ans 에 더해주기만 하면 된다.
int ans = 0;
// 뒤에서부터 순회
for(int j=N; j>0; j--)
{
if(arr[j-1] >= arr[j])
{
ans += arr[j-1] - arr[j] + 1;
arr[j-1] = arr[j] - 1;
}
}
이렇게 모든 경우에 대한 ans 를 계산하여 출력만 하면 된다.
static int N;
static int[] arr;
static void input()
{
N = scan.nextInt();
arr = new int[N+1];
for(int i=1; i<=N; i++) arr[i] = scan.nextInt();
}
static void pro()
{
int ans = 0;
// 뒤에서부터 순회
for(int j=N; j>0; j--)
{
if(arr[j-1] >= arr[j])
{
ans += arr[j-1] - arr[j] + 1;
arr[j-1] = arr[j] - 1;
}
}
System.out.println(ans);
}
급하게 조사하고 정리하다보니 부족하거나 틀린 내용이 있을 수도 있는데 댓글로 달아주시면 감사하겠습니다!