문제 링크 : programmers.co.kr/learn/courses/30/lessons/62048
위 사진은 문제의 예시이다.
처음에는 규칙을 찾기 위해 고민을 했다.
그러다 똑같은 형태의 다각형이 반복된다는 것을 알아냈고 가로길이(W)와 세로길이(H)의 최대공약수만큼 반복 된다는 것을 알게 되었다.
그래서 다각형 한개를 기준으로 봤을때 몇개의 사각형이 포함되는지를 계산하고 거기에 최대공약수를 곱하면 되겠다고 생각했다.
위의 예시는 W = 8, H = 12이고 최대공약수(GCD)는 4이다.
반복되는 다각형의 가로길이는 (W/GCD = 8/4) 2이고 세로길이는 (H/GCD = 12/4) 3이다.
최대공약수로 나눈.. 즉, 반복되는 다각형 한개 기준으로 보면 각 다각형의 가로 길이와 세로길이의 최대공약수는 1이다.
이렇게 최대공약수가 1일 때는 가로길이 + 세로길이 - 1 만큼 선이 사각형을 지나간다.
그러므로 다음과 같은 식이 성립한다.
다각형 한개에서 제외되는 사각형의 수 = (W/GCD + H/GCD - 1) * GCD = W + H - GCD
그러므로 위의 예시는 8 * 12 - (8 + 12 - 4) = 96 - 16 = 80이 되는 것이다.
그래서 이 문제를 푸는 핵심 수식은
W * H - (W + H - GCD)
이다.
using namespace std;
long long getGCD(long long a, long long b)
{
if(a % b == 0) {
return b;
}
return getGCD(b, a%b);
}
long long solution(int w,int h) {
long long W = w, H = h;
// (w/g+h/g-1)g=w+h-g
long long answer = W * H - (W + H - getGCD(W, H));
return answer;
}
'알고리즘' 카테고리의 다른 글
[프로그래머스] 여행경로 (C/C++) (0) | 2020.12.30 |
---|---|
[프로그래머스] 줄 서는 방법 (C/C++) (0) | 2020.12.22 |
[프로그래머스] 도둑질 (C/C++) (0) | 2020.12.20 |
[프로그래머스] 가사 검색 (C/C++) (0) | 2020.12.19 |
[프로그래머스] 4단 고음 (C++) (0) | 2020.12.18 |
댓글