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

문제 링크

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

코드

java

class Solution{
    public long solution(int w, int h){
    
    return (long)w*h-(w+h-gcd(w,h));
    }
    
    public int gcd(int x, int y){
    
    if(x==y){
    return x;
    } else if(x>y){
    return (x%y==0)? y : gcd(y, x%y);
    } else {
    return (y%x==0)? x : gcd(x, y%x);
    }
}

python

def gcd(x,y):
  if x==y: return x
  elif x>y: return y if x%y==0 else gcd(y, x%y)
  else: return x if y%x==0 else gcd(x,y%x)

def solution(w,h):
    
    return w*h - (w+h-gcd(w,h))

풀이

멀쩡한 정사각형의 개수를 구하기 위해 전체 정사각형의 개수에서 손상된 정사각형의 전체 개수를 빼기로 했다.
손상된 정사각형의 전체 개수를 구하기 위해 다음의 과정을 거쳤다.

대각선과 어떤 정사각형 s의 교점은 다음 두 가지 상태 중 하나이다.
1) 교점이 정사각형의 꼭짓점에 존재한다.
2) 교점이 정사각형의 모서리에 존재한다.

전체 도형에서 시작점과 끝점을 제외하고 1번 상태의 교점이 존재한다면 손상된 사각형들이 이루는 영역은 서로 동일한 단위 영역들로 나눌 수 있다. 그리고 이렇게 나눠진 단위 영역들의 개수는 w, h의 최대공약수와 같다.

이를 통해 손상된 정사각형(B)의 전체 개수는 단위 영역에서의 손상된 정사각형의 개수(B')에 최대공약수 gcd를 곱한 것과 같다는 것을 알 수 있다.

달리 말해 단위 영역 내에서는 그 영역의 시작점과 끝점을 제외하고는 어떤 교점도 꼭짓점에 존재하지 않는다.
다음과 같은 경우를 생각해보자.

w=85, h=65인 전체 도형에서 최대공약수 5를 이용하여 단위 영역으로 나누었다 생각해보자. 위는 그 단위 영역 중 하나의 모습이다.
단위 영역 내에서는 시작점과 끝점을 제외하고는 꼭짓점을 정확히 지나는 교점은 존재할 수 없다. 즉 대각선은 (시작점, 끝점을 제외하면) 항상 정사각형의 모서리를 지난다.

시작점에서 끝점으로 가기 위해서는 반드시 정사각형의 윗모서리를 지나는 지점이 발생한다. 끝점에 도달하기 위해서는 반드시 위로 향해야 하기 때문에 대각선은 h'을 1단위로 끊어 수평선을 그렸다고 생각했을 때 각 수평선을 반드시 한번씩 지난다.

이렇게 대각선이 어떠한 정사각형의 윗모서리를 지나는 지점을 표시하면 다음과 같다.

해당 지점(빨간색 동그라미)은 위아래로 손상된 정사각형이 붙어 있는 지점이다. 이 지점들을 기준으로 형광색이 칠해진 손상된 정사각형들 중 일부를 아래로 내려 다음처럼 배치해보자.

그러면 두 가지 부분으로 나눌 수 있다.
하나는 아래쪽에 긴 직사각형 형태로 배치된 부분, 하나는 위에서 대각선과의 교점이 윗모서리에 위치하는 지점을 포함한 정사각형들.

긴 직사각형 형태로 배치된 손상된 정사각형의 개수는 보다시피 w'와 같다.
또 띄엄띄엄 배치된 정사각형들의 총 개수는 h'-1과 같다. (h'을 0~h'이 표시된 눈금자라고 생각해보자. 양 끝단을 제외하고 1~(h'-1)에 해당하는 눈금의 개수는 h'-1이다.)(윗모서리의 교점 위치는 매번 다를 수 있다. 하지만 이 도형에서 대각선은 우상향이고 반드시 매 행마다 한번씩 위로 올라가야 한다. 대각선이 좌상향이어도 마찬가지 논리를 적용할 수 있다.)

즉 단위 영역에서 손상된 정사각형의 개수는 w'+h'-1이라는 것을 알 수 있다.
(이 때 '단위 영역에서'라는 부분이 중요하다. 상술했듯 단위 영역에서는 시점과 종점을 제외하고는 꼭짓점 교점이 존재하지 않는데 꼭짓점 교점이 존재하게 되면 위의 수식을 적용할 수 없다. 때문에 단위 영역을 만들기 위해 최대공약수를 이용하는 방식이 필요하다.)

정답
따라서 정답은 다음과 같이 구할 수 있다.

멀쩡한 사각형의 개수 = (wh)-gcd(w'+h'-1) = (wh) - gcd(w/gcd + h/gcd -1) = (w*h) - (w + h - gcd)

후기

• 최대공약수를 구하는 방법은 '유클리드 호제법'을 참고했다.
• 첫 시도에 성공한 것은 아니다. 첫 시도는 시점으로부터 w방향으로 한칸씩 이동할 때마다 h 방향으로 기울기만큼 증가하는 값을 구하고 해당 값들에 대해 floor, ceil을 적용하여 누적 count를 구하려 했다.
  이 방법은 우선 최종적으로 사용한 방식에 비해 시간이 오래 걸렸고, (아직도 이유는 모르겠지만)잘못된 값이 출력되었다.
• 이번 문제는 코딩 자체보다 생각하는 부분이 중요했다.