알고리즘/[ Baekjoon ]

[ BOJ ][JAVA][14929] 귀찮아 (SIB)

kim.svadoz 2021. 5. 6. 23:07
반응형

www.acmicpc.net/problem/14929

 

14929번: 귀찮아 (SIB)

n과 xi가 주어짇나. n은 10만 이하ㅇ고, xi는 젗ㄹ댓값이 100이하인 정수디이다.

www.acmicpc.net

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 512 MB 761 334 271 43.499%

문제

∑1≤a<b≤nxaxb

입력

n과 xi가 주어짇나. n은 10만 이하ㅇ고, xi는 젗ㄹ댓값이 100이하인 정수디이다.

출력

위에서 구하란 걸 구하면 된ㄷ.

예제 입력 1

3
1 -2 3

예제 출력 1

-5

코드

/*
    구간 합 알고리즘
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p14929 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // n 이 10만 이하.
        int[] arr = new int[n + 1];
        int[] sum = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            sum[i] = sum[i - 1] + arr[i];
        }

        long ans = 0;
        for (int i = 1; i < n; i++) {
            int v = getSubSum(i + 1, n, sum);
            ans += v * arr[i];
        }
        System.out.println(ans);
    }

    static int getSubSum(int l, int r, int[] sum) {
        return sum[r] - sum[l - 1];
    }

}
반응형

'알고리즘 > [ Baekjoon ]' 카테고리의 다른 글

[ BOJ ][JAVA][15649] N과 M(1)  (0) 2021.05.06
[ BOJ ][JAVA][15486] 퇴사 2  (0) 2021.05.06
[ BOJ ][JAVA][11659] 구간 합 구하기 4  (0) 2021.05.06
[ BOJ ][JAVA][7579] 앱  (0) 2021.05.06
[ BOJ ][JAVA][5582] 공통 부분 문자열  (0) 2021.05.06