[kotlin 알고리즘] 정N각형의 삼각 분

문제



주어진 문자열을 회전하며 괄호가 적절한지 검사하는 문제이다.

---

풀이

해당 문제는 언뜻보면 최단거리 문제같지만 DP로 해결할 수 있다.

먼저  N각형을 삼각형을 분할하는 방법이다. 이 때 분할된 삼각형 사이의 거리가 최솟값이 되어야 한다.

가장 쉬운 방법은 한 꼭지점을 잡아 그 지점부터 자신과 인접하지 않은 꼭짓점으로 이동하며 선을 그으면 최솟값의 거리를 가지는 삼각형들로 분할할 수 있다.

 

8각형의 경우 다음과 같이 분할할 수 있다.

이런식으로 분할하며 경우의 수를 모두 적어보면 다음과 같은 경우들을 얻는다

N

3 - 0

4 - 1

5 - 2

6 - 2

7 - 3

8 - 3

9 - 4

10 - 4

11 - 4

12 - 4

13 - 5

14 - 5

...

이 때 n각형을 계속그리면서 발견한 규칙이 있었는데 3 * 2^i 의 n각형은 i-1의 n각형으로 분리된다는 점이었다.

예를들어 6각형을 나눴을 땐 3각형으로 나뉘었다.

이를 생각하며 결과를 분석하였더니 다음과 같은 규칙을 발견하였다.

3 - 0

6 - 2

12 - 4

24 - 6

48 - 8

 

i가 증가할수록 거리값은 2씩 늘어난다.

그렇다면 해당 구간 사이 즉 3, 6사이 , 6, 12 사이 등... 에서 1이 늘어나는 구간과 2가 늘어나는 구간을 나눌 수 있다는 말이다.

 

예를들어 6과 12사이에서는 7~8까지는 2+1 = 3 의 거리를 갖고 8~11은 2+2 =4 의 거리를 갖는다.

이 구간의 규칙은 3을 index 0 6을 1 12를 2 로 놓았을 때

(3,6,12,...) + 2^index 까진 1이 증가하고 그 이후는 2가 증가한다.

 

그렇다면 3, 6, 12 ... 의 값을 미리 알고있다면 해당 구간 사이의 값도 바로 알 수 있다.

이를 코드로 구현하면 다음과 같다.

 

 

val N = readLine().toInt()
var idx = 3
var cnt = 0
var tmp =1

먼저 N각형을 받아온다.

그 후 idx, cnt, tmp 값들을 선언해주는데

각각 3, 6, 12,...를 저장할 변수, 해당 변수의 인덱스, 구간의 인덱스이다.

 

 

 

when(N) {
        3 -> println(0)
        else -> {
            val dp = mutableListOf<MutableList<Int>>()
            while (true) {
                if (idx <= 1000000) {
                    dp.add(mutableListOf(idx, cnt, tmp))
                    idx *= 2
                    cnt += 2
                    tmp *= 2
                } else {
                    break
                }
            }

그 후 N값에 따라 코드를 진행한다.

N이 3일경우에는 예외적으로 0을 출력한다.

 

만약 아닐경우는 dp배열을 선언하는데 이 dp 배열은 3, 6, 12, 24...1000000까지의 거리를 저장하는 역할을 한다.

idx가 1000000까지 반복하면서 값들을 저장한다. 이 때 배열에는 idx, cnt, tmp값이 한 묶음으로 들어간다.

 

for (i in 0 until dp.size) {
                val (a, b, c) = dp[i]
                if (a == N) {
                    println(b)
                    break
                }

                if (a < N && N < a * 2) {
                    if (N <= a + c) {
                        println(b + 1)
                        break
                    } else {
                        println(b + 2)
                        break

                    }
                }
            }

 

그 후 dp 배열의 사이즈만큼 반복문을 진행한다.

 

먼저 a, b, c 즉 idx, cnt, tmp값들을 dp배열에서 뺀 후 

idx값이 N값과 동일하다면 즉 N이 3, 6, 12... 와 같은 숫자라면

cnt값을 출력한다.

 

만약 idx < N < idx * 2 즉 구간 사이의 값이라면

1 또는 2를 더해줘야 한다.

이 때 더해주는 구간은 tmp값이 가지고있으므로

idx + tmp 값보다 작거나 같다면 1을 더해주고, 크다면 2를 더해준 후 출력한다.

---

코드

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


fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val N = readLine().toInt()
    println(N)
    var idx = 3
    var cnt = 0
    var tmp =1

    when(N) {
        3 -> println(0)
        else -> {
            val dp = mutableListOf<MutableList<Int>>()
            while (true) {
                if (idx <= 1000000) {
                    dp.add(mutableListOf(idx, cnt, tmp))
                    idx *= 2
                    cnt += 2
                    tmp *= 2
                } else {
                    break
                }
            }

            for (i in 0 until dp.size) {
                val (a, b, c) = dp[i]
                if (a == N) {
                    println(b)
                    break
                }

                if (a < N && N < a * 2) {
                    if (N <= a + c) {
                        println(b + 1)
                        break
                    } else {
                        println(b + 2)
                        break

                    }
                }
            }
        }
    }

}