자바 [Algorithm] 누적합 - 백준 2851 슈퍼 마리오

1. 문제

2. 접근법

마리오는 받은 점수의 합을 최대한 100에 가깝게 만든다고 한다.

하지만 100에 가까운 수가 2개라면 ex) 98, 102 마리오는 큰 값을 선택한다.

 

1. 반복문으로 1~10까지 sum에 점수를 더한다.

2. if(sum > 100)이 되면

3. 100 - (sum - mario[i]) < sum - 100 등호가 성립되면 sum -= mario[i] 해주고 break

3. 코드

package week08;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        int[] mario = new int[10];
        int sum = 0;

        for(int i=0; i<10; i++){
            mario[i] = Integer.parseInt(bufferedReader.readLine());
        }

        for (int i = 0; i < 10; i++) {
            sum += mario[i];

            if(sum > 100) {
                if (100 - (sum - mario[i]) < sum - 100) {
                    sum -= mario[i];
                    break;
                }
            }
        }

        System.out.println(sum);
    }
}

 

시간 복잡도

O(n)