[ 백준 14929 ] 귀찮아(SIB) (Kotlin)

 

14929번: 귀찮아 (SIB)

 

문제 이해

• 각각의 두 원소끼리 곱한 합을 구하는 문제
• 즉, n=3이고 x1, x2, x3가 있으면 x1x2 + x1x3 + x2x3를 구하라는 문제이다.
• 해당 문제에선 규칙을 찾는게 중요 + 누적 합으로 계산 최적화

 

풀이

n=4일 때를 가정하면 아래와 같은 식을 얻을 수 있다.

 ex) n=4 { x1 x2 x3 x4 }
  
  x1x2 + x1x3 + x1x4 + x2x3 + x2x4 + x3x4
  => x1(x2+x3+x4) + x2(x3+x4) + x3(x4)

  규칙을 보면 x1부터 차례대로 자신을 제외한 다른 원소들의 합과 곱해지는 것을 볼 수 있다.
  
  공통 인수로 나온 원소는 다음 계산에서 제거되며, 그 다음 원소가 공통 인수가 되고 다른 원소들의 합과 곱해지는 규칙
  
  누적 합을 사용하여 더하는 부분의 계산을 최적화하면 시간 초과 없이 문제를 풀 수 있다.

 

코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val n = readLine().toInt()
    val list = readLine().split(" ").map { it.toLong() }

    val array = Array<Long>(n+1){0}
    var sum:Long = 0

    list.forEachIndexed { index, i -> array[index + 1] = array[index] + i }
    list.forEachIndexed { index, i ->
        sum += i * (array[n] - array[index+1])
    }

    println(sum)
}