[프로그래머스] 멀쩡한 사각형 (Kotlin)

프로그래머스 : 멀쩡한 사각형 (Kotlin)

문제

문제 확인하기

풀이

가로 3, 세로 4 크기의 직사각형이 주어졌다고 하자.

이 직사각형을 대각선 양 끝 꼭짓점을 기준으로 자르는 것을 좌표상에 표시하면 아래와 같이 표현할 수 있다.

양 끝 꼭짓점([0, 0]과 [3, 4])을 서로 이었을 때 나오는 대각선은 y = (4/3) * x 방정식으로 표현할 수 있다.
우리는 이 대각선을 기준으로 우측에 있는 삼각형에 몇 개의 1 * 1 크기의 정사각형이 존재하는지 세고, 이 값의 2배를 정답으로 반환하면 된다.

여기서 1 * 1 크기의 정사각형이 몇 개가 존재하는지 어떻게 셀 수 있을까?

먼저 x 좌표의 범위가 0 ~ 1인 부분을 보자.
여기는 정사각형이 존재하지 않는다.

다음 x 좌표의 범위가 1 ~ 2인 부분을 보자.
x 좌표가 1일 때 y 좌표는 4/3 이다.
x 좌표가 2일 때는 확인할 필요가 없다.
x 좌표가 1일 때의 y 좌표 4/3 위로는, 대각선이 1 * 1 정사각형을 모두 잘라버려 더 이상 정사각형이 아니게 된다.

따라서 x 좌표가 1일 때의 y 좌표값을 자연수로 내림한 값 만큼의 1 * 1 크기의 정사각형이 존재하게 된다.
여기서 4/3을 자연수로 내림하면 1이 되고, 1 * 1 크기의 정사각형이 1개 존재한다.

위 내용을 통해 x 좌표의 범위가 2 ~ 3인 부분도 확인해보자.
x좌표가 2일 때 y 좌표는 8/3 이다.
8/3 위로는 x 좌표 3 이내에 정사각형이 존재하지 않는다.

따라서 x 좌표가 2일 때의 y 좌표값을 자연수로 내림한 값이 x 좌표값 2에서 3 이내에 존재하는 정사각형의 개수이다.
여기서 8/3을 자연수로 내림하면 2이 되고, 1 * 1 크기의 정사각형이 2개 존재하는 것이다.

이제 위 과정을 통해 구한 정사각형의 값을 모두 더하면 큰 직각삼각형 하나에 존재하는 1 * 1 정사각형의 개수(sum)가 된다.

3 * 4 크기의 직사각형을 대각선으로 잘랐기 때문에 이 직각삼각형이 2개 존재하게 되므로, sum * 2가 문제가 요구하는 정답이 된다.

아래는 코틀린으로 작성한 코드이다.

class Solution {
    fun solution(w: Int, h: Int): Long {
        return (0L until w.toLong()).reduce { total, i -> total + (h.toLong() * i) / w } * 2
    }
}