(JAVA) 백준 2847번 : 게임을 만든 동준이

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

11725번: 트리의 부모 찾기

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);
}

 

 

 

급하게 조사하고 정리하다보니 부족하거나 틀린 내용이 있을 수도 있는데 댓글로 달아주시면 감사하겠습니다!