[Programmers] 멀쩡한 사각형 (Java)

🔗 문제링크

https://programmers.co.kr/learn/courses/30/lessons/62048

📃 문제 설명

가로길이 w와 세로길이h의 직사각형을 대각선으로 자른다고 했을때, 남은 1x1격자 갯수

🔎 문제풀이 도출하기

1. 영역의 갯수 구하기

위의 그림이 예로 주어진다. 먼저 규칙을 생각하기 위해 좌표를 적어봤다.

(h,w)
1번 영역: (1,1) (2,1) (2,2) (3,2)
2번 영역: (4,3) (5,3) (5,4) (6,4)
3번 영역: (7,5) (8,5) (8,6) (9,6)
4번 영역: (9,7) (11,7) (11,8) (12,8)

그림의 영역 번호를 좌표로 적어봤고 1-2-3-4 영역이 3,2씩 증가하는 것을 알 수 있었다. 왜 3,2일까?

영역을 나눌 때에는 최대공약수로 나눌 수 있는데, 이때 그림의 w와 h는 각각 8과 12이므로 gcd = 4이다.

주어진 h(12)를 gcd(4)로 나누면 3, w(8)을 gcd(4)로 나누면 2이다.

여기까지가 직사각형에서 못쓰는 격자의 영역이 몇개로 나누어지는지 도출해본 결과이다.

2. 영역 내의 답이되는 격자 갯수
다음으로, 영역의 갯수를 구했다면 각 영역에서 못쓰는 격자의 갯수가 몇 개가 되는지 어떻게 알 수 있을까? 몇 가지 예를 생각해보면

n = w/gcd, m=h/gcd
위의 예에서 영역에서 대각선으로 잘라 못쓰게된 격자의 갯수는 n(가로)+m(세로)-1 이 됨을 알 수 있다. 대각선은 n만큼, m만큼 가야하는데, 여기서

이 영역이 겹치기 때문에 n+m-1 해준 것!

마지막으로 그렇다면 전체 못쓰게된 격자의 갯수를 구해보자

3. 공식 도출

1에서 영역의 갯수를 먼저 구했다. 갯수는 w와 g의 최대공약수로 구했다.

2에서 영역 내의 격자갯수를 구했다. w/gcd+h/gcd-1

(w/gcd + h/gcd -1)*gcd
정리해보면

w+h-gcd 가 되는 것을 알 수 있다!

다른 블로그를 참고해서 똑같이 구해보면,

ref) https://taesan94.tistory.com/55

w(7)와 h(14)의 gcd = 7이고 그림에서 영역의 갯수 = 7개
영역 내의 격자 갯수 = w/gcd+h/gcd-1 => 2+1-1 = 2개

(w/gcd +h/gcd-1)*gcd = w+h-gcd = 14

가 되는 것을 알 수 있다.

💻 코드

class Solution {
    static int gcd(int a, int b){
        while(b!=0){
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }
    public long solution(int w, int h) {
        long answer = 1;
        int gcd_v = gcd(w,h);
        answer = ((long)w*(long)h)-((long)w+(long)h-(long)gcd_v);
        return answer;
    }
}