[프로그래머스] 멀쩡한 사각형 (문제 설명, 해결 과정, 코드 전문, c++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 프로그래머스의  멀쩡한 사각형 문제입니다.

 

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

 

 

 

 

해결 과정

 

이번 문제는 일정한 패턴이 가로 세로의 최대공약수만큼 반복됨을 알 수 있습니다. 그리고 해당 패턴의  직선에 닿는 사각형들의  갯수는 패턴 내 직선의 시작점과 끝점까지의 최단거리와 관련됨을 볼 수 있다.

아래의 그림을 보면 패턴이 가로 2 세로 3으로 반복된다. 시작점과 끝점의 최단거리를 구하기 위해서는 가로와 세로를 더한 값이 나오며, 이 최단거리까지의 방향성을 생각해서 첫 블록부터 접근하면 가로와 세로를 더한 값에 1을 뺀 셈이다.

 

 

 

다음 그림과 같이 간선이 노드의 수보다 하나 적은 것과 유사한 개념이다.

코드 전문

 

 

#include <cmath>

using namespace std;

long long GCD(long long a, long long b){
    long long big, small;
    big = max(a, b);
    small = min(a, b);
    
    long long mod = big%small;
    
    while(mod>0){
        big = small;
        small = mod;
        mod = big%small;
    }
    
    return small;
}

long long solution(int w,int h) {
    long long answer = 1;
    long long prod = (long long)w*h;   
    long long gcd_v = GCD(w, h);
    answer = prod - w - h + gcd_v;   
    return answer;
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

어렵네요.. 이런 문제는 많이 풀어봐야겠습니다.

 

 

 

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.