[구현] 멀쩡한 사각형

접근

멀쩡한 사각형

이 문제는 큰 직각삼각형으로 만들 수 있는 가장 작은 직각 삼각형 즉 큰 직각 삼각형의 최대공약수로 나눈 변을 가진 삼각형을 구한뒤
거기서에서 제거되는 사각형의 수를 곱하자까지는 접근했습니다.

하지만 몇 개의 사각형이 제거되는지에 대한 규칙을 발견하지 못해
문제를 시간내에 풀지 못했습니다.

다른 분의 풀이를 보고 가장 작은 직각 삼각형의 두변을 더한 뒤 1을 빼야한다는 것을 알았습니다.
하지만 제가 실제로 이 문제를 테스트에서 만난다면 위 규칙을 발견할 수 있을지 모르겠습니다.

생각해보았을 때 문제에 주어진 예시를 보고 먼저 규칙을 발견하고
이게 다른 경우에도 맞는지를 확인하는 쪽으로 접근하는 것이 나아보입니다!

그러나 위 규칙에도 불구하고
몇 개의 테스트에서 실패가 떴습니다.
원인을 찾아보니 자료형에 문제가 있었습니다.

프로그래밍 언어들은 대부분 곱하기 연산을 할 때 자료형을 곱하는 데이터의 자료형을 따라갑니다.
long answer = w*h; 는 곱하고 답을 구한 후 int형에 저장 후 long형으로 캐스팅하여 값을 넣어주게 됩니다.
곱하기 연산 후 데이터가 int형의 범위를 벗어나는 오버플로우가 날 수 있습니다.
<출처: 프로그래머스 멀쩡한 사격형 질문하기 부분에서>

질문하기 탭에서 원인을 발견했습니다.
제가 int로 선언된 w와 int로 선언된 h를 곱하면 그 결과가 long으로 저장될 것이라고 생각했는게 그게 아니었습니다. w*h는 int로 저장되고 그 이후에 long형으로 캐스팅된다고 합니다.

따라서 w*h가 int의 범위를 넘어서면 오버플로우가 발생하는 경우가 있고 오버플로우가 발생된 그 값이 long형으로 저장될 수도 있습니다.

그래서 다음과 같이 풀이를 수정하였습니다.

  // 총개수
        long newW= (long)w;
        long newH= (long)h;
        long total  = newW*newH;

풀이는 다음과 같습니다.

풀이

class Solution {
    public long solution(int w, int h) {
        long answer = 1;
        // 가로길기 Wcm , 세로길이 Hcm인 직사각형 종이가 있다.
        // 종이에는 가로, 세로
        // 이 격자선을 따라 격자를 잘라 사용
        // 누군가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았다
        // 몇 개의 격자 정사각형이 만들어지는가 
        // 가로의 길이 W, 세로의 길이 H : 1억 이하의 자연수
        
        // 가장 작은 삼각형의 대각선을 구한다 => 최대 공배수
        // 그 대각선이 지나는 사각형의 개수를 구한다.
        // 현재 삼각형의 대각선 /가장 작은 삼각형의 대각선 * 사각형의 개수 =c
        // 총 사각형의 개수 - c
        
        // 총개수
        long newW= (long)w;
        long newH= (long)h;
        long total  = newW*newH;
        // 작은 삼각형 만들기
        int smallTri = gcd(w,h);
        long new_w =w/smallTri;
        long new_h =h/smallTri;
        // 작은 삼각형에서 삭제되는 사각형의 수
        long remove = new_w+new_h-1;

        
        answer=total-remove*smallTri;
        
        
        
        
        return answer;
    }
    
   static int gcd(int A, int B){
        if(B==0) return A;
        return gcd(B,A%B);
    }
}