백준 1364 울타리 치기 코틀린

백준 1364번 울타리 치기

출처 - https://www.acmicpc.net/problem/1364

문제

육각형 블록들로 이루어진 RPG 세계가 있다. 그 세계에 나라를 세우려고 하는 군주 캐릭터 송유진은 일반 블록을 울타리 블록으로 바꿀 수 있는 아이템을 N개 가지고 있다. 유진이가 이 N개의 아이템을 이용해서 점령할 수 있는 최대의 영토의 넓이를 구해보자. 울타리 안에 둘러싸인 블록들은 당연히 넓이에 포함 시키고, 울타리를 세운 블록도 넓이에 포함을 시킨다. 울타리는 항상 이어져 있어야 하며, 맵의 넓이는 무한하다.

입력

첫 줄에는 송유진이 가지고 있는 아이템의 수 N(1≤N≤1,000,000)이 주어진다.

출력

N개의 아이템을 이용하여 점령할 수 있는 최대의 블록 수를 출력한다.

풀이

수학 문제, 특히 도형에 관련된 것은 규칙을 찾는 것이 우선인 것 같다.

이 문제의 경우, 직접 그려보면서 규칙을 찾았다.

1 -> 1 1
2 -> 2 1
3 -> 3 1
4 -> 4 1
5 -> 5 1
6 -> 7 2
7 -> 8 1
8 -> 10 2
9-> 12 2
10 -> 14 2
11 -> 16 2
12-> 19 3
13 -> 21 2
14 -> 24 3
15 -> 27 3
16 -> 30 3
17 -> 33 3
18 -> 37 4
19 -> 40 3
20 -> 44 4
21 -> 48 4
22 -> 52 4
23 -> 56 4
24 -> 61 5
25 -> 65 4
26 -> 70 5
27 -> 75 5
28 -> 80 5
29 -> 85 5
30 -> 91 6

이렇게 정육각형일때 증가량이 1씩 증가하고, 정육각형보다 n이 1 클때는 증가량이 일시적으로 1 감소한다.

그림판을 이용해 그려보면 n이 1 증가할 때마다 가장 큰 변을 바깥쪽으로 옮기고 추가된 1개의 울타리를 이용해 이어주게 되는 것을 알 수 있다.

코드

import java.io.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    var answer = 1L
    var x = 1L
    for(i in 2..n){
        if(i%6==0) x++
        if(i%6==1) answer--
        answer += x
    }
    println(answer)
}