[Kotlin, B2] 백준 31215번 이상한 섞기 연산

출처: unsplash.com

 

이상한 섞기 연산(31215번)

Bronze 2

#애드 혹

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

 

문제 내용

 

 

문제 접근

1부터 n까지 시작하는 수열 B가 있다. n이 5면 1, 2, 3, 4, 5로 구성되는 수열이 된다.

k까지의 수열이 있을 때, k의 약수에서 가장 큰 2의 제곱수가 l이다.

예를 들어 k = 4일 때, 4의 약수는 1, 2, 4이고, 여기서 가장 큰 2의 제곱수인 l은 4이다(2의 2승).

k가 3인 경우에는 3의 약수 1, 3에서 가장 큰 2의 제곱수는 2의 0승인 1이 된다.

l을 구하고 나면 수열의 k번째 index와 l번째 index를 교환한다.

아 과정이 문제에 언급된 이상한 섞기 연산이다.

 

이상한 섞기 연산을 통해 변경한 수열에서 1이 들어 있는 index를 구해 보자.

사진 1-1

수열의 변동은 1부터 k까지 반복되기 때문에 기존에 변경된 수열을 그대로 사용하게 된다.

k = 1의 경우 약수가 1 하나밖에 없어서 가장 큰 2의 제곱수는 1이 되기 때문에 수열이 변하지 않는다.

k = 2의 경우에는 약수가 1, 2이고 가장 큰 제곱수가 2이지만, k와 l이 같아서 값을 변경하지 못해 수열이 변하지 않는다.

k = 3인 경우는 약수가 1, 3이고 가장 큰 제곱수가 1이라서 k번째 index의 값과 l번째 값이 바뀌기 때문에 위 표와 같은 형태가 나온다.

4, 5, 6의 경우에도 k와 l번째 index의 값을 변경해 주는 작업을 해주었다.

위 표를 보면 공통점이 있다.

1의 값이 k가 1, 2일 때를 제외하면 모두 3번째 index에 있다.
k가 1, 2일 때는 무조건 1번째 index에 존재한다.

 

애초에 1이 3으로 이동하게 되면서 k 또는 l이 3이 되어야 1의 위치가 변하게 되는데,

1이 3번째 index로 이동하는 경우가 k가 3일 때이고, 그 이후로는 l이 3이 돼야 하는데 l은 2의 제곱수여야 해서 홀수가 올 수 없다.

그래서 저렇게 일일이 계산할 필요 없이 규칙을 찾아서 정답을 구할 수 있다.

 

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val case = readLine().toInt()
    val res = StringBuilder()

    for (i in 0 until case) {
        val num = readLine().toInt()

        if (num >= 3) res.append("3\n")
        else res.append("1\n")
    }

    println(res)
}

 

문제 풀이

num이 3보다 클 때만 3을 출력하고, 1, 2일 때는 1을 출력하면 문제를 해결할 수 있다.

StringBuilder를 쓴 이유는 출력이 별도의 줄로 출력하라 해서 쓴 것이다.

println을 써도 문제가 없더라.

위가 println()을 쓴 거고, 아래는 StringBuilder를 쓴 것이다.

확실히 StringBuilder가 빠르긴 하다.

 

 

문제 해결 과정

구현 자체는 브론즈 5지만 k가 3 이후일 때는 2의 거듭제곱이 절대 3이 나올 수가 없다는 것을 알아야 하는 문제라서 브론즈 2로 레이팅 된 듯하다.

나도 처음에 문제를 볼 때 이걸 다 반복해서 구현해야 하는지 생각을 했었다.

하지만 브론즈 문제가 그럴 리가 없다 생각해서 해설지에서 힌트를 찾아봤는데도 이해하기가 힘들어서

사진 1-1의 표를 만들어서 규칙을 찾게 되었다.

머리가 잘 굴러간다면 날먹 문제가 되고 아니라면 힘들 수 있는 문제.