[코딩 테스트] 프로그래머스 연습 문제 - 멀쩡한 사각형

프로그래머스 level2 문제인 멀쩡한 사각형 문제를 풀어보았습니다.

 

 

 

프로그래머스 연습 문제 - 멀쩡한 사각형

 

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

프로그래머스

 

 

 

 문제 설명

 

 

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

 

문제 그림

 

 

 

 제약 사항

 

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

 

 

 

 

 

 코드

 

W와 H가 1억까지 갈 수 있으므로 시간복잡도를 고려해야 합니다. 또한 문제의 규칙을 이해해야 합니다. 

대각선으로 잘랐을 때, 현재 W, H 의 관계와 정답과의 관계를 설정할 수 있어야 합니다. 두 개의 숫자를 쪼개어서 규칙을 찾아야 한다 라는 점에서 최대공약수를 활용한 문제임을 짐작할 수 있었고 이를 활용하여 규칙을 생각해 낼 수 있었습니다.

개인적으로 시간이 조금 걸려서 다른 분의 문제풀이를 조금 참고하였습니다. 

 

 

using namespace std;

int gcd(int a, int b){
    int t = 0;
    while(b){
        t = a % b;
        a = b;
        b = t;
    }
    return a;
}

long long solution(int w, int h)
{
    long long answer = 0;
    int t = gcd(w, h);
    answer = (long long)((long long)w * (long long)h) - (w + h - t);
    return answer;
}

 

 

 

 

 결론

 

최대공약수를 활용한 다는 것은 쉽게 생각해 낼 수 있었지만 결국 정답을 찾기 위해서 여러 가지 케이스를 고민하여 정답을 찾아내야 합니다. 이런 것은 정말 똑똑한 분이 아니라면 많은 문제 풀이 경험을 통해서 얻을 수 있을 것 같습니다.