[백준] 10986번 : 나머지 합 - 코틀린

10986번: 나머지 합

❓ 문제 풀이

• 누적 합을 이용한 문제이다.
• 처음에 생각했던 건 구간 합을 이용하는 것이었다. 실제로 문제에도 구간의 합이라 써있어서...
• 구간 합을 구하여 M으로 나눈 나머지가 0이면 되는 것이다.
• sum이라는 Array에 N개의 수 구간 합을 만들면 i ~ j 까지의 구간 합은 sum[j] - sum[i-1]이다.
• 따라서 (sum[j] - sum[i-1]) % M이 0인 경우를 찾으면 된다.
  • 위의 식은 sum[j] % M == sum[i - 1] / M 으로 바꿔도 성립된다.
  • 아래의 블로그 작성자 분이 정말 세세하게 설명해주셔서 도움이 될 것 같다.
  • https://nahwasa.com/entry/%EC%9E%90%EB%B0%94-%EB%B0%B1%EC%A4%80-10986-%EB%82%98%EB%A8%B8%EC%A7%80-%ED%95%A9-java

 

 

 

❓내 코드

import java.util.Scanner

fun main() = with(Scanner(System.`in`)) {
    val N = nextInt() // 숫자의 개수
    val M = nextInt() // 나눌 수
    val reminder = IntArray(M)
    
    // 나머지를 더할 변수
    var sum = 0
    
    for(i in 1 .. N){
        sum += nextInt() % M
        reminder[sum % M]++
    }
    
    var answer = reminder[0].toLong()
    for(i in 0 until M){
        val cnt = reminder[i]
        answer += cnt.toLong() * (cnt - 1) / 2
    }
    
    println(answer)
}