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

문제

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

프로그래머스

문제 분석

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

 

 

특정 알고리즘을 사용하기 보다는 문제에서 규칙을 찾아 풀어야 하는 문제 같다.

 

대각선의 길이와 사각형의 개수의 상관관계가 있을까?

아니면 좌표로 생각했을 때 기울기도 상관관계가 있을 수 있을 거 같다.

 

문제 접근

좌표로 생각해 보았을 때 해당 직선은 (0, 0), (2, 3), (4, 6), (6, 9), (8, 12) 좌표를 지난다.

그리고 해당 좌표 사이에 4개의 망가진 사각형이 나온다.

 

이 특정 패턴을 분석해보자.

(0, 0) 을 제외한 이 직선에서 나올 수있는 좌표는 4개이고 이는 패턴이 4번 반복되는 것을 볼 수 있다.

4는 주어진 가로, 세로의 최대 공약수이다.

 

그럼 특정 패턴 안에서 사용하지 못하는 사각형의 개수를 구할 수 있다면 문제를 풀 수 있다.

 

특정 패턴 안에서 사각형의 개수는 다음과 같은 특징을 갖는다.

가로 + 세로 - 1

위의 예시에서 한 패턴 안의 망가진 사각형은 3+2-1= 4 개이다.

 

그럼 계산 식을 세우면 (전체 사각형 개수) - (패턴의 가로 + 패턴의 세로 -1) * 패턴의 개수 가 된다.

위의 예시로는  8*12 - (2+3-1 ) * 4 = 80 이다.

 

최대 공약수가 1인 경우에도 문제가 없을까?

최대 공약수가 1인 경우에는 특정 패턴이 존재하지 않는다.

이런 경우는 패턴이 1개 있는 경우로 (가로+세로-1) * 1 로 계산이 되어 문제가 없다.

 

 

 

코드

import java.util.*;
class Solution {
    public long solution(int w, int h) {
        int gcd = gcd(w, h);
        
        return (long)w*h - (w/gcd + h/gcd - 1) * gcd;
    }
    
    int gcd(int a, int b){
        if(b==0){
            return a;
        }
        
        return gcd(b, a%b);
    }
}