Programmers[62048] - 멀쩡한 사각형[Level2]

링크

프로그래머스

 

문제설명

• -

문제풀이

• W * H - (W+H-GCD(W,H))

기본

W를 고려할 때

H를 고려할 때

W, H 모두 고려했을 때

• 겹쳐서 중복으로 빼지는 빨간 칸이 생긴다. 빨간 칸의 갯수의 규칙성을 찾으면 된다.

• 4=GCD(8, 12)

• 작은 검은 사각형의 w=2, h=3이다.

• W/w = H/h가 된다.

• 대각선이 변을 지나지않고 점을지난다는것은 딱 나누어떨어진다는 뜻이고, w,h를 제외(w,h만큼 반복이동하면) 나누어떨어진다는 뜻이다. 최대공약수의 개념.

문제코드

public class Solution62048_멀쩡한_사각형 {
    public static int gcd(int a, int b) {
        if(a>b) {
            if(a%b==0) {
                return b;
            }
            else {
                return gcd(a,a%b);
            }
        }
        else {
            return gcd(b,a);
        }
    }

    public static long solution(int w,int h) {
        long answer = w*h - w - h + gcd(w,h);

        return answer;
    }

    public static void main(String[] args) {
        System.out.println(solution(8, 12));
    }
}

아쉬운점

• solution(int,int)이지만 W*H가 int 범위를 넘어갈 수 있으므로 아예 (long,long)으로 바꿔서 푸는게 나았음

잘한점

• O(N)
  • W, H <=10^8 이므로
  • 하나하나 카운트하려면 시간초과
  • 규칙성을 찾아 다른 방법으로 접근하려고 했음