[Kotlin, S3] 백준 32186번 역시 내 이세계 수열은 잘못됐다

출처: unsplash.com

 

역시 내 이세계 수열은 잘못됐다(32186번)

Silver 3

#수학 #그리디 알고리즘

https://www.acmicpc.net/problem/32186

 

문제 내용

 

 

문제 접근

각 위치에 맞는 index의 값 2개를 +k 연산과 +1 연산을 이용해 같은 값으로 만들어야 하는 최소 연산 횟수를 출력한다.

 

값 2개 중 작은 값을 큰 값에 딱 맞게 만드는 방법과

작은 값에 +k 연산을 반복해 큰 값보다 커지도록 만들고 큰 값에 +1 연산을 해서 값을 맞추는 방법이 있다.

 

예를 들어 k가 7이고 5와 28이 매칭되는 값일 때

5를 28로 만들기 위해서는 5에 7을 3번 더하고 1을 2번 더하면 28이 된다(연산 횟수 5번).

그리고 5에 7을 4번 더하면 33이 되는데, 28에 1을 5번 더하면 두 값이 모두 33이 된다(연산 횟수 9번).

 

위의 2가지의 방법 중에서 더 적은 연산 횟수인 경우만 택해서 total 연산 횟수에 더해주면 된다.

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max
import kotlin.math.min

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    val (n, k) = bf.readLine().split(" ").map { it.toInt() }
    val a = bf.readLine().split(" ").map { it.toInt() }
    var cnt: Long = 0

    for (i in 0 until n / 2) {
        val target = a.lastIndex - i

        if (a[i] != a[target]) {
            val big = max(a[i], a[target])
            val small = min(a[i], a[target])

            val cnt1 = (big - small) / k + (big - small) % k
            val divValue = (big - small) / k + 1
            val cnt2 = divValue + (k * divValue + small - big) % k

            cnt += min(cnt1, cnt2)
        }
    }

    println(cnt)
}

 

문제 풀이

매칭되는 big과 small을 정의하고

 

cnt1은 small에만 연산을 진행해 big과 동일한 값을 만드는 방법의 연산 횟수를 구할 수 있고

cnt2는 small에 +k 연산을 진행사고 big에 +1 연산을 진행한 방법의 연산 횟수를 구할 수 있다.

divValue를 정의해 small에 k를 몇 번을 더해야 big을 넘어가는지 정의하고, k * divValue에 small을 더하게 되면 k를 divValue번 더한 small의 값이 나오는데, big을 빼고 나머지 연산을 진행하면 +1 연산의 횟수를 구할 수 있게 된다.

 

 

문제 해결 과정

cnt2를 구하기 위해 처음에는 수학 공식을 쓰지 않고 while 문을 사용해 횟수를 구해줬는데, 시간 초과가 발생했었다.

while문 대신에 수학 공식을 활용해 문제를 해결할 수 있었다.