[Programmers / Java] 멀쩡한 사각형

문제링크

 

코드

class Solution {
    public long solution(int w, int h) {
        long gcd_result = gcd(w,h);

        long w1 = Long.parseLong(String.valueOf(w));
        long h1 = Long.parseLong(String.valueOf(h));

        long patton = (w1 + h1) - gcd_result;
        long answer = (w1 * h1) - (patton);

        return answer;
    }
    
    public long gcd (long a, long b){
        if((a % b) == 0) return b;
        return gcd(b,(a%b));
    }
}

 

이 문제를 풀면서 3시간정도 고민하고 다른 사람의 풀이를 참조해서 풀었습니다.

 

어떤점이 어려웠나?

불규칙한 직사각형을 구할 때 사용할 수 없는 정사각형의 개수를 구하는 것이 어려웠습니다.

 

이건 제가 2 x N의 직사격형들을 보고 패턴을 알아보려고 그린것입니다.

 

3 x N의 직사각형도 측정해봤습니다.

 

아래는 각 직사각형마다 어떤 패턴이 있을까 고민해본 흔적입니다.

w	h	사용못하는 블럭
2	3	4
2	4	4
2	5	6
2	6	6
2	7	8
2	8	8
2	9	10
2	10	10
2 x N 직사각형들 입니다.

 

w	h	사용 못하는 블럭
3	4	6
3	5	7
3	6	6
3	7	9
3	8	10
3	9	9
3	10	12
3	11	13
3	12	12

 

어떤 규칙을 발견할꺼 같으면서도 애매한 숫자 패턴이 이어졌습니다. 여기서 눈에 띄였던건 w,h가 서로 최소공배수를 가지면 사용 못하는 블럭에 변화가 생겼습니다.

대각선을 보면 정확히 가운데를 뚫고 지나가니 사용못하는 블럭의 개수는 줄어들었습니다.

 

그럼 어떻게 다른 직사각형의 사용못하는 블럭의 개수를 구하는가... 여기서 한참을 해맸습니다. 피타고라스를 써볼까? 다른 방법이 있나? 고민하다가 결국 다른사람의 풀이를 참조했습니다.

 

 

직사각형은 대각선이 그어지면 세로줄은 최소 1칸은 차지하게 됩니다. (+ h)

그리고 가로줄도 최소 1칸은 차지하게 됩니다.( +w)

현재 사용하지 못하는 블럭의 개수는 (w + h) 입니다.

빨간색이 w , 노란색이 h라고 치면 시작지점의 1개의 블록이 겹치게 됩니다.

그러므로 사용못하는 블럭의 개수는 (w + h - 1) 이 됩니다.

이러한 방식으로 사용하지 못하는 블럭의 개수를 구하게 됩니다. 이 공식이 직관적이지 않아서 처음에 이해하기 어려웠습니다.

 

문제를 풀 때 문제를 접근하고 패턴을 익히고 공식을 빨리 찾아내는것이 중요하다고 생각됩니다.

 

 

그러면 8 x 12 직사각형이니 [20 - 1] = 19 해가지고 19개를 못쓰는 건가? 라고 생각할 수 도 있습니다.

직사각형의 대각선이 가로지르는 사각형들은 일정한 패턴이 반복됩니다. 녹색칠한 부분의 패턴이 4번 반복됩니다.

왜 4번 반복하냐면은 8 x 12 직사각형의 최대공약수만큼 반복하고 있습니다.

 

그렇다면 전체 사용못하는 블럭의 개수에서 최대공약수 만큼 빼면 되겠죠?

사용못하는 블럭의 개수 공식은 [ w + h - 최대공약수] 입니다.

위 예시로 [20 - 4] 가 되는것입니다.

 

예를들어 보겠습니다. 왼쪽은 3 x 5 직사각형, 오른쪽은 3 x 6 직사각형 입니다.

 

3 x 5 직사각형는 패턴이 반복되지 않습니다.

3 x 6 직사각형은 1 * 2 블럭이 3번 반복되고 있습니다.

 

3 x 5의 사용못하는 블럭의 개수는 [3 + 5 - 1] = 7 입니다.

3 x 6의 사용못하는 블럭의 개수는 [3 + 6 - 3] = 6 입니다.

 

결국 중요한건 사용못하는 블럭의 개수 공식을 구하는것 같습니다. 패턴이 얼마나 반복되는지는 파악할 수 있었지만 그전의 블럭을 어떻게 구하는지 몰라서 오랜시간이 걸렸습니다.