Baekjoon(Kotlin) - 10986. 나머지 합

URL : https://www.acmicpc.net/problem/10986

10986번: 나머지 합

 

[ RESULT ]

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (N, M) = br.readLine().split(" ").map { it.toInt() }
    val arr = br.readLine().split(" ").map { it.toLong() }

    val prefixSum = LongArray(N + 1)
    for (i in 0 until N) {
        prefixSum[i + 1] = prefixSum[i] + arr[i]
    }

    val remainderCnt = mutableMapOf<Long, Long>()
    var cnt = 0L

    for (i in 0 until N + 1) {
        var remainder = prefixSum[i] % M.toLong()
        if (remainder < 0) { remainder += M.toLong() }
        if (remainderCnt.containsKey(remainder)) {
            cnt += remainderCnt[remainder]!!
            remainderCnt[remainder] = remainderCnt[remainder]!! + 1
        } else { remainderCnt[remainder] = 1 }
    }

    bw.write(cnt.toString())
    bw.newLine()

    br.close()
    bw.flush()
    bw.close()
}

 

나머지 합을 이용했다.

 

해결 방법을 스스로 발견하지 못하여 여러 블로그를 통해서 풀이를 이해했다.

 

구간 합의 나머지를 Key로 이용한다.