Junku's 개발 블로그

문제 풀이 아이디어는 Python 풀이와 같습니다. 단지.. 지금 약간 혼동이 오는게,,, 자바와 비슷한 코드로 작성했는데, 코틀린은 시간 초과가 나고 자바는 통과되네요. 다른 방식을 생각해야 할 것 같은데,,, 좀 어렵네요. import java.util.Scanner fun main(args: Array) { val sc = Scanner(System.`in`) val n = sc.nextInt() val m = sc.nextInt() val arr = IntArray(n+1) {0} for (i in 1..n) arr[i] += arr[i-1] + sc.nextInt() var i: Int var j: Int for (k in 0 until m) { i = sc.nextInt() j = sc.nex..

문제 풀러 가기! 전형적인 DP 문제로 입력값이 많기 때문에 구간 마다 더하면 안됩니다. 처음 배열을 입력 받을 때 해당 배열의 누적합을 기록해준 다음 이를 이용하여 구간합을 구해주어야 합니다. 0번 index부터 차례로 하나씩 누적시키면 연산 횟수는 최대 10만번이기 때문에 1초 100,000,000을 넘지않으면서 구할 수 있습니다. 즉 i와 j의 구간합은 j번째 누적합 - i-1번째 누적합을 의미하므로 배열에 접근할 때는 시간 복잡도가 O(1)이기 때문에 빠르게 연산이 가능합니다. 이 문제에서는 O(n**2)이 아니라 O(n)으로 문제를 풀어야 한다는 것이죠. 결국 해당 문제를 종합적으로 살펴봤을 때, n 최대 10만개, m 최대 10만개로 20만번의 순회 끝내 모든 답이 도출되게 됩니다. 아래는 제..