멀쩡한 사각형(Summer/Winter Coding(2019))

문제 링크

코딩테스트 연습 - 멀쩡한 사각형

 

풀이

해당 문제를 자세히 보면 부분으로 쪼갤 수 있는 단서를 발견한다.

사실 이 문제를 풀 때, 1억이하의 자연수를 준 것으로 보아 일단 long long으로 변수를 해야겠고 해당 문제는 점화식의 문제가 아닌가 생각되어 직접 몇 개 그려서 규칙을 찾아냈다.

일단 부분적인 모양은 자세히 보면 →↓ 로 왼쪽 위 꼭지점에서 오른쪽 아래 꼭지점으로 가는 것과 같다.

즉, width + heigth -1의 개수이다.

부분적인 것에서의 개수를 알아냈으니 부분으로 나누는 기준을 알아야 한다.

이는 "최대 공약수"이다.(사실 많이 노가다했다. 문제에서는 최대공약수로 바로 되지만 w, h를 홀수로 그리면 애매하다)

따라서, w, h를 최대공약수로 나누어 smallW, smallH를 구해 width+height-1을 적용하고 최대 공약수를 다시 곱하면 빠지는 개수가 나오고 이를 전체 개수에서 빼주면 답이다.

 

 

#include <iostream>

using namespace std;

// 반복되는 것이 보임
// 기울기는 일정하다.
// 부분으로 쪼갬 * 갯수(가로를 최대공약수로 나눈 갯수 - 1)
// 기울기를 기약분수로(최대공약수로 나눠줌)
// 기울기 = -h/w

long long gcd(long long a, long long b)
{
    long long c;
    while(b!=0)
    {
        c = a%b;
        a = b;
        b = c;
    }
    return a;
}

long long solution(int w,int h) {
    long long answer = 1;
    long long smallW = (long long)w / gcd(w, h);     // 반복되는 작은 w
    long long smallH = (long long)h / gcd(w, h);     // 반복되는 작은 h
    
    answer = smallW + smallH - 1;
    answer *= w/smallW;  // 반복되는 부분의 갯수를 곱해줌
    answer = (long long)w * (long long)h - answer;
    return answer;
}