[JAVA/수학] 프로그래머스 멀쩡한 사각형

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/62048?language=java

코딩테스트 연습 - 멀쩡한 사각형

 

2. 풀이

직사각형의 높이가 h, 너비가 w이라고 하자.

w와 h의 최대공약수가 1보다 클 경우 직사각형 내부의 꼭짓점을 지난다. 

• gcd가 1인 경우
  • 대각선이 가로줄과 세로줄을 한번씩 지날 때마다 대각선이 만나는 사각형의 갯수가 증가하는데, 총 (h-1)의 가로줄과 (w-1)의 세로줄을 지나게 된다. 맨처음 시작한 사각형을 더하면, 대각선이 그어진 타올의 갯수는 w + h - 1이다.

  • 

• gcd가 1이 아닌 경우
  • gcd가 1이 아닌 경우, 직사각형 내부의 꼭짓점을 w,h의 최대공약수가 1인 지점에서 만나게 된다. 즉, w/gcd와 h/gcd이 너비와 높이인 사각형에서 대각선이 그어진 타올의 갯수가 gcd배 반복된다,
  • 따라서, 대각선이 그어진 타올의 갯수는 ((w/gcd) + (h/gcd) - 1) * gcd = w + h - gcd 다.

문제에서는 대각선을 지나지 않는 사각형을 구해야 하므로 (전체 사각형 갯수) - (대각선을 지나는 사각형 갯수)로 답을 구한다.

 

3. 코드

class Solution {
    
    public int getGCD(int a, int b){
        if(b == 0) return a;
        return getGCD(b, a%b);
    }
    
    public long solution(int w, int h) {
        
        return ((long)w*(long)h) - ((long)w + (long)h - getGCD(w, h));
        
    }
}​

 

4. 비슷한 문제

백준 2168 타일위의 대각선

https://www.acmicpc.net/problem/2168

2168번: 타일 위의 대각선