문제 62068. 멀쩡한 사각형

문제 링크

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

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

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

입력

• 가로의 길이 W
• 세로의 길이 H

입력 제한

• W, H : 1억 이하의 자연수

입력 예제

// input
8		// W
12		// H

// ans
80

 

풀이 방식

사각형에서 찢어진 부분을 유심히 보면 패턴이 존재한다는 것을 알 수 있다. 예시를 통해 알아보자.

예시로 주어진 12*8 사각형의 찢어진 모습을 보면 번개 모양으로 총 4번 찢어져있다. 이걸 보고 '다른 사각형들도 비슷한 패턴으로 찢어지지 않을까?' 하는 생각이 들었고, 더 자세히 보니 모든 번개 모양이 3*2사각형에서 찢어져있는 것을 알 수 있었다. 즉, 단위 사각형에서 찢어진 패턴이 반복적으로 발생한다는 것! 단위 사각형과 단위 사각형에서 찢어진 부분의 개수를 알 수만 있다면 해당 문제는 쉽게 풀릴 것으로 보인다. 

 

단위 사각형과 단위 사각형에서 찢어진 부분의 개수 구하기

단위 사각형을 구하는 법은 간단하다. w와 h의 최대공약수를 구하고, 각각 최대공약수 만큼 나눠주면 단위 사각형의 크기가 된다. 문제는 찢어진 부분의 개수인데, 모든 단위 사각형에 적용할 수 있는 공식이 보이지않아 일단 다양한 크기의 단위 사각형을 예시로 확인해보았다.

왼쪽부터 3*3, 3*4, 3*5 사각형

 

위의 예시를 그리다보니, 하나의 패턴이 보이게 된다. 바로 찢어진 부분의 개수가 단위 사각형의 w+h-1개라는 것! 3*4 단위 사각형은 3+4-1로 6개인 것을 확인할 수 있다.  3*5 단위 사각형은 3+5-1로 7개인 것을 확인할 수 있다. 몇 개의 추가적인 단위 사각형을 그려보았지만 동일하게 w+h-1가 성립되는 것을 확인하였고, 이로써 찢어진 부분의 개수를 구하는 공식을 알아내었다. (3*3에는 적용되지 않는데, 그 이유는 3*3은 단위 사각형이 아니기 때문. 단위 사각형은 1*1이다)

 

적용

이제 코드만 적어주면 된다. 최대 공약수를 구하는 방식은 유클리드 호제법을 사용하였고(getShared_n함수) 위에서 알아낸 단위 사각형에서 찢어진 부분 개수 공식을 적용하여 답을 구해냈다. 

정답 코드 

#include <algorithm>
#include <bits/stdc++.h>

using namespace std;


long long getShared_n(long long w, long long h){
  
    while (h != 0) {
        long long temp = h;
        h = w % h;
        w = temp;
    }
    
        
    return w;
}

long long solution(int w, int h) {
    
    long long answer = -1;
    
    long long max_shared_n = getShared_n(w, h);
    long long long_w = w;
    long long long_h = h;
    
    long long unit_rip = long_w / max_shared_n + long_h / max_shared_n -1;
    
    answer = long_w * long_h - max_shared_n * unit_rip;
    
    return answer;
}