2903번: 중앙 이동 알고리즘

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

2903번: 중앙 이동 알고리즘

언어 : Kotlin

 

문제 설명 :

상근이는 친구들과 함께 SF영화를 찍으려고 한다. 이 영화는 외계 지형이 필요하다. 실제로 우주선을 타고 외계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG처리를 하려고 한다.

외계 지형은 중앙 이동 알고리즘을 이용해서 만들려고 한다.

알고리즘을 시작하면서 상근이는 정사각형을 이루는 점 4개를 고른다. 그 후에는 다음과 같은 과정을 거쳐서 지형을 만든다.

1. 정사각형의 각 변의 중앙에 점을 하나 추가한다.
2. 정사각형의 중심에 점을 하나 추가한다.

초기 상태에서 위와 같은 과정을 한 번 거치면 총 4개의 정사각형이 새로 생긴다. 이와 같은 과정을 상근이가 만족할 때 까지 계속한다.

아래 그림은 과정을 총 2번 거쳤을 때까지의 모습이다.

 

초기 상태 - 점 4개	1번 - 점 9개	2번 - 점 25개

상근이는 어떤 점은 한 개 보다 많은 정사각형에 포함될 수 있다는 사실을 알았다. 메모리 소모량을 줄이기 위해서 중복하는 점을 한 번만 저장하려고 한다. 과정을 N번 거친 후 점 몇 개를 저장해야 하는지 구하는 프로그램을 작성하시오.

 

• 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 15)
• 첫째 줄에 과정을 N번 거친 후 점의 수를 출력한다.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
1	9
2	25
5	1089

풀이 : 

import java.io.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    var n = br.readLine().toInt()
    var differ = 3

    if (n >= 1) {
        var increase = 1

        for (i in 1 .. n) {
            increase *= 2
            differ += increase
        }

        increase = 1
        
        for (i in 1 .. n) {
            increase *= 4
        }

        n = increase
    }

    bw.write("${n + differ}")
    bw.flush()
    bw.close()
}

 

처음 주어진 정보는 다음과 같다.

정사각형 (1 - 4 - 16 - ?? - ?? - ????)

점의개수 (4 - 9 - 25 - ?? - ?? - 1089)

 

이 정보 속에서 규칙을 찾아서 그걸 그대로 코드로 풀어썼다.

정사각형은 n을 거칠 때마다 4배씩 늘어난다. (1 - 4 - 16 - 64 - 256 - 1024)

점은 점 자체만으로는 규칙성을 찾지 못하겠다 (4 - 9 - 25 - ? - ? - 1089)

 

따라서 다른 곳에서 규칙성을 찾아봤다.

정사각형 개수와 점의 개수 차이는 다음과 같다. (3 - 5 - 9 - ?? - ?? - 65)

이 개수 차이에서 규칙을 찾아내면 다음과 같다.    (2 - 4 - "8" - "16" - 32) "" 안의 숫자는 예측

 

n을 거칠 때마다 점은 '증가량 * 2'씩 늘어난다.

증가량은 예제로 주어진 0, 1, 2 상태로 확인이 가능한데, 이는 현재 점의 개수 - 이전 점의 개수라고 할 수 있다.

 

이를 가지고 예제로 주어진 n 5 -> 1089를 적용해보면 예측한 규칙이 맞다는 것을 알 수 있다.

최종적으로는 다음과 같은 형태를 가진다.

 

	초기 (n = 0)	n = 1	n = 2	n = 3	n = 4	n = 5
정사각형 개수	1	4	16	64	256	1024
차이점	3	5	9	17	33	65
점의 개수	4	9	25	81	289	1089