백준 1540 정사각형의 개수 Kotlin (dp)

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

1540번: 정사각형의 개수

문제

세준이는 2차원 평면에 N개의 점을 찍었다. 그리고 나서 정사각형의 개수를 세려고 한다.

정사각형의 개수란, 세준이가 찍은 서로 다른 N개의 점을 꼭짓점으로 하며, 모든 변은 축에 평행한 서로 다른 정사각형을 모두 센 것이다.

세준이는 정사각형의 개수를 최대로 하려고 한다.

N이 주어졌을 때, 정사각형의 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 이 값은 0보다 크거나 같고, 1000000보다 작거나 같은 값이다.

출력

첫째 줄에 정사각형의 개수의 최댓값을 출력한다.

알고리즘 분류

• 수학
• 조합론

풀이

수학, 조합론으로 분류되어 있는 문제이다.

수학? 조합론? 몰라 그냥 냅다 규칙 찾아버렸다.

우선 모든 점을 활용했을 때 정사각형의 모양이 나오는 경우 먼저 살펴보자.

점이 4개, 9개, 16개, 25개~~~

즉, 어떤 수 i의 제곱수인 경우 변의 길이가 i-1인 정사각형이 나온다.

이 경우만 먼저 정사각형의 수를 세보면,

점이 1개일 땐 정사각형의 개수가 0

점이 4개일 땐 정사각형의 개수가 1

점이 9개일 땐 정사각형의 개수가 1 + 4

점이 16개일 땐 정사각형의 개수가 1 + 4 + 9

점이 25개일 땐 정사각형의 개수가 1 + 4 + 9 + 16이다.

오오 이것이 바로 수학인 것 같다.

정사각형의 개수를 구하는 공식이 있나 보다.

어찌 됐든 규칙을 찾았으니 i의 제곱수인 경우는 답을 쉽게 찾을 수 있다.

나머지 경우는 어떨까?

 

점을 하나씩 추가하며 정사각형을 그려본 결과,

다음과 같이 점을 찍어나가는 것이 정사각형의 개수를 최대로 할 수 있었다.

즉, 점이 4개일 때, 6개일 때, 8개일 때, 9개일 때 모습은 다음과 같다.

쩜 4개

 

쩜 6개

 

쩜 8개

 

쩜 9개

오오 뭔가 이걸 이용하면 될 거 같다. 

점이 1,2,3개일 땐 사각형이 나올 수가 없고,

4개일 때부터 정사각형을 그릴 수 있다.

5개일 때도 정사각형 1개,

6개일 때는 정사각형 2개,

대충 20개까지만 구해보자.

 

점의 개수     정사각형 개수

    1                0

    2                0

    3                0

    4                1

    5                1

    6                2

    7                2

    8                3

    9                5

    10               5  

    11               6

    12               8

    13               8

    14               9

    15               11

    16               14

    17               14

    18               15

    19               17

    20               20

 

여기까지 왔다면 눈치 빠른 사람은 뭔가 규칙을 찾았을 것이다.

 

점이 16개인 상황에서 점이 25개인 경우까지 구해보자.

우선 점이 21개일 때 까진 3*3 정사각형의 우측에 점을 추가한다.

점이 17개일 땐 3*3 정사각형의 개수와 같다.

점이 18개일 땐 점이 17개일 때의 정사각형 개수에서 1개 추가된다. (크기 1인 정사각형 1개)

점이 19개일 땐 점이 18개일 때의 정사각형 개수에서 2개 추가된다. (크기 1인 정사각형 1개, 크기 2인 정사각형 1개)

점이 20개일 땐 점이 19개일 때의 정사각형 개수에서 3개 추가된다. (크기1인 정사각형 1개, 크기 2인 정사각형 1개, 크기 3인 정사각형 1개)

점이 21개일 땐 점이 20개일 때의 정사각형 개수에서 0개 추가된다.

점이 22개일 때부턴 3*3 정사각형의 아래에 점을 추가한다.

점이 22개일 땐 점이 21개일 때의 정사각형 개수에서 1개 추가된다. (크기 1인 정사각형 1개)

점이 23개일 땐 점이 22개일 때의 정사각형 개수에서 2개 추가된다. (크기 1인 정사각형 1개, 크기 2인 정사각형 1개)

점이 24개일 땐 점이 23개일 때의 정사각형 개수에서 3개 추가된다. (크기1인 정사각형 1개, 크기 2인 정사각형 1개, 크기 3인 정사각형 1개)

점이 25개일 땐 5의 제곱수이기 때문에 이미 구해놨다.

 

위를 식으로 표현하면, n이 i*i과 같다면, 

dp[n]~ dp[n+i -1]까지는 

dp[n+1] = dp[n] + 0

dp[n+2] = dp[n+1] + 1

dp[n+3] = dp[n+2] + 2

~~~

dp[n+i-1] = dp[n+i-1-1] + i-1

이 되고,

dp[n+i] = dp[n+i-1] + 0 // 우측 대각 아래에 점을 찍은 경우

 

여기까지가 점을 우측에 찍은 경우,

그리고 점을 아래에 찍는 경우도 위의 과정을 반복하면 된다.

 

허접한 그림으로 설명하느라 애썼다.

최선을 다했다.

 

 

//이해가 안 된다면 댓글 남겨주시기 바랍니다!!!

//c++ 코드도 필요하면 업로드 하겠습니다.

코드

import kotlin.math.*

val dp = IntArray(1000001)
fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    var n = br.readLine().toInt()
    for(i in 2 .. 1000){
        dp[i*i]= dp[(i-1)*(i-1)]+(i-1)*(i-1)
    }
    var idx =0
    var plus =2
    for(i in 5 .. 1000000){
        //점의 개수가 x*x꼴이면 스킵
        if(dp[i]!=0){
            plus = sqrt(i.toDouble()).toInt()
            idx=0
            continue
        }
        //점을 우측 대각 아래 찍은 경우, 방향 전환
        if(idx==plus){
            dp[i] = dp[i-1]
            idx=1
        }
        //0부터 plus-1까지 더한다.
        else{
            dp[i] = dp[i-1]+idx
            idx++
        }
    }

    write("${dp[n]}")

    close()
}