[A&I Code Camp] Day39

✍   Kotlin을 PS 문제 풀기

소속중인 A&I 동아리에서 코딩역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는 kotlin을 기반으로 작성합니다.

13900번

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

이 문제는 N개의 정수를 받아 서로 다른 위치의 두 수를 뽑아 모든 경우의 곱의 합을 구하는 문제입니다.

Solve

0. 이 문제는 순서쌍의 곱의 공식을 잘 알아야합니다.
   예를 들어 입력 2를 생각해보며 모든 공식을 세워 봤을 때
   (1 * 2) + (1 * 3) + (1 * 4) + (2 * 3) + (2 * 4) + (3 * 4)의 식이 나오는데
   이것을 정리하면 (1*(2+3+4)) + (2*(3+4)) + (3+4) 이 됩니다.
   이것을 잘 기억해두고 해결을 해봅시다.
1. 순서쌍의 공식을 사용하기 위해 배열 그대로 받아야 합니다.
2. 누적합을 구해주는데 범위가 정수의 갯수 범위가 $N(2 ≤ N ≤ 100,000)$에 수 범위가 0이상 10,000 이기 때문에 LongArray로 받아줍니다.
3. (1*(2+3+4)) + (2*(3+4)) + (3+4) 이 공식을 생각하며
   arr[x] * (pSum[n] - pSum[x+1])으로 치환하여 result안에 더해줍니다.

import java.io.StreamTokenizer

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())){
    fun nextInt() : Int{
        nextToken()
        return nval.toInt()
    }

    val n = nextInt()

    val arr = IntArray(n){
        nextInt()
    }

    val pSum = LongArray(n+1){
        0
    }

    repeat(n){
        pSum[it+1] = pSum[it] + arr[it]
    }

    var result = 0L
    for(x in 0 until n){
        result += arr[x] * (pSum[n] - pSum[x+1])
    }
    println(result)
}