[Programmers] Lv.2 - 멀쩡한 사각형 (Kotlin)

문제 링크

문제 링크

문제 설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한사항

W, H : 1억 이하의 자연수

입출력 예

W H result
8 12 80

입출력 예 설명

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

풀이 언어

Kotlin

풀이 방법

일단 이런 문제는 규칙을 찾아야 한다. 하지만 규칙을 찾지 못해 구글링으로 해결한 문제이다. Level 2 였는데 큰 코 다쳤다... 기존에 내가 풀었던 방법은 주어진 h와 w가 같은 경우 정사각형이고 이 때 사용할 수 없는 정사각형의 수는 항상 h와 같았다. 핵심은 직사각형에서의 사용할 수 없는 정사각형의 수를 찾아내는 것이었는데 이걸 찾아내지 못했다. 위 그림에도 나와있는 것처럼 특정한 패턴이 연속적으로 반복되는데 이 패턴의 규칙을 찾지 못했다. 정답은 최대공약수였다.

일단 동일한 패턴이 시작되고 종료되는 지점을 적어보자. 좌측 상단을 (0,0)으로 잡고 우측 하단으로 내려갈수록 좌표를 +한다고 가정.

• (0,0) -> (2,3) -> (4,6) -> (6,9) -> (8, 12) 로 증가한다.

• x의 경우 2씩, y의 경우 3씩 증가하고 있다.

• 이는 곧 (h / 최대공약수) , (w / 최대공약수) 만큼 증가하고 있다.

• 이 때 영향을 받는 정사각형의 개수는 (h / 최대공약수) + (w / 최대공약수) + 1 라고 볼 수 있다.

• 하지만 이건 동일한 패턴 1개의 예시이고 이런 패턴이 최대공약수 만큼 존재한다. 따라서 결과적으로 h + w + 최대공약수 가 영향을 받는 정사각형의 개수가 된다.

이제 직접 적용해보자.

위의 패턴에서의 h는 12, w는 8이므로 최대 공약수는 4.
일단 대각선을 그리기 전의 정사각형의 개수는 12 * 8 = 96.
여기서 h + w - 최대 공약수 를 빼주면 96 - 16 = 80. 정답이다.

결과

코드

class Solution {
    fun gcd(a : Long, b : Long) : Long {
        if (b == 0.toLong()) {
            return a
        } else { 
            return gcd(b, a%b)
        }
    }
    
    fun solution(w: Int, h: Int): Long {
        var answer: Long = 0
        
        var big : Long = 0
        var small : Long = 0
        
        if (w > h) {
            big = w.toLong()
            small = h.toLong()
        } else { 
            big = h.toLong()
            small = w.toLong()
        }
        
        answer = big * small - (big + small - gcd(big, small))
 
        return answer
    }
}

알게 된 점

• Level 2 라고 얕보지 말자.

• 로직이 맞는데 특정 테케에서 걸린다? 자료형을 다시 보자.