99클럽 코테 스터디 16일차 TIL

백준 - 2847번

풀이

최적의 방법을 찾기 위해 각 레벨마다 바로 다음 레벨의 점수와 비교해 필요한 만큼만 감소시키는 방식으로 접근해야 한다.

 

주어진 점수의 마지막에서부터 시작하여, 각 레벨의 점수가 이전 레벨보다 작거나 같아야 한다는 조건을 만족하도록 점수를 줄여나가야 한다.

만약 현재 레벨의 점수가 이전 레벨보다 크거나 같으면, 이전 레벨의 점수를 현재 레벨보다 작도록 감소시킨다.

전체 감소 횟수를 최소화하기 위해 현재 레벨의 점수에서 1을 감소시킨다.

 

예를 들어, 예제 입력 1번은 3, 4, 5 형식으로 만들어야 한다.

• 마지막 5(last)부터 반복문을 시작하고, 이전 점수(before)와 비교한다.
• last 가 before 보다 작거나 같다면, before 의 실제 점수 값(scores[i -1])에 last - 1 을 매핑해준다.
• before - scores[i - 1] 의 값을 감소 횟수에 저장한다.

구현

import java.io.*;
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] scores = new int[N];
        for (int i = 0; i < N; i++) {
            scores[i] = Integer.parseInt(br.readLine());
        }

        int result = 0; // 감소 횟수
        for (int i = scores.length - 1; i > 0; i--) {
            int last = scores[i];
            int before = scores[i - 1];

            if (last <= before) {
                scores[i - 1] = last - 1;
                result += (before - scores[i - 1]);
            }
        }

        System.out.println(result);
        br.close();
    }
}

---

백준 2847번 - 게임을 만든 동준이

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