[백준] 2851번 - 슈퍼 마리오 [Java]

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

 

[백준] 2851번 - 슈퍼 마리오 [Java]

[백준] 2851번 - 슈퍼 마리오 [Java]

[백준] 2851번 - 슈퍼 마리오 [Java]

---

1.  아이디어

 

누적합을 활용한 브루트포스 알고리즘으로 해결할 수 있다.

---

2. 문제풀이

 

슈퍼 마리오는 처음부터 중단하기 전까지 버섯을 집어야하므로 이를 누적합 배열로 구했다. 누적합을 구하면서 바로 브루트포스 알고리즘으로 정답 및 100과의 차이를 저장하는 ans, diff 변수를 활용해서 100과의 차이의 절댓값이 더 작으면 해당 수를 정답으로 하고 절댓값이 같으면 정답과 해당 수 중 더 큰 수를 저장하도록 구현했다.

---

3. 코드

 

import java.io.*;

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

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

        int ans = 0;
        int diff = 100;

        int[] dp = new int[1 + 10];
        for (int i = 1; i <= 10; i++) {
            dp[i] = dp[i - 1] + arr[i - 1];

            if ((Math.abs(dp[i] - 100) < diff) || (Math.abs(dp[i] - 100) == diff && (dp[i] > ans))) {
                ans = dp[i];
                diff = Math.abs(dp[i] - 100);
            }
        }

        System.out.println(ans);
    }
}

---

4. 후기