1292번: 쉽게 푸는 문제

문제 출처 : https://www.acmicpc.net/problem/1292

1292번: 쉽게 푸는 문제

언어 : Kotlin

 

문제 설명 :

동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다.

이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다.

하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자.

• 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다.
• 첫 줄에 구간에 속하는 숫자의 합을 출력한다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
3 7	15

다른 사람의 풀이 : 

import java.io.BufferedWriter
import java.io.OutputStreamWriter

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (x1, x2) = readLine().split(" ").map { it.toInt() }
    val arr = arrayListOf<Int>()

    for (i in 1 .. 100) {
        for (j in 1 .. i) arr.add(i)
    }

    var sum = 0
    for (i in x1 - 1 until x2) sum += arr[i]

    bw.write("$sum")
    bw.flush()
    bw.close()
}

 

시도하던 풀이가 있었으나 어느 시점 이후 나아가질 못해 포기했다

 

시도하다 포기한 풀이 : 

import java.io.BufferedWriter
import java.io.OutputStreamWriter

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (x1, x2) = readLine().split(" ").map { it.toInt() }
    val arr = IntArray(1000) { 0 }

    var cnt = 0
    for (i in arr.indices) {
        if (i == 0) arr[i] = 1 else arr[i] = arr[i - 1] + cnt
        cnt++
    }

    var start = 0
    var sum = 0
    var arrr = intArrayOf()
    for (i in arr.indices) {
        if (x1 >= arr[i]) {
            start = i + 1


        }

        repeat(x1 - arr[i]) {
            sum += start
        }
    }

    bw.write("$start\n")
    bw.write("$sum")
    bw.flush()
    bw.close()
}

 

접근하던 방법은 다음과 같다.

구간마다 규칙성이 존재할 것이라고 생각했고, 시작하는 부분의 Index가 순서대로 증가함을 알아냈다

1	->	2	->	4	->	7	->	11
	1		2		3		4

숫자 = 시작 인덱스

1 = 1

2 = 2

3 = 4

5 = 11

6 = 16

7 = 22

8 = 29

 

1 2 4 7 11 16 22 29 37 46 56 67
 1 2 3 4   5   6   7   8   9  10  11

 

따라서 비교하며 연산을 반복문으로 표현해주면 되리라 생각했다