- 문제
[문제링크]
가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.
- 제한사항
W, H : 1억 이하의 자연수- 입출력 예
-전체코드
class Solution {
public long solution(int w, int h) {
long answer = 1;
int factor = Gcd(w, h);
answer = (long) w * h - (w + h - factor);
return answer;
}
public int Gcd(int a, int b) {
int r = a % b;
if(r == 0) {
return b;
}
else {
return Gcd(b, r);
}
}
}- 막혔던 점 & 해결방법
입출력 예에서 보듯 가로 W와 세로 H가 서로소가 아니라면 두 수의 최대공약수 만큼 일정한 패턴을 반복하는 것을 볼 수 있습니다.
반복 되는 패턴의 직사각형에서 사용할 수 없는 정사각형의 개수를 알아내는 과정에서 막혔었습니다. 반복되는 빨간 직사각형을 자세히 살펴본 후 다음과 같은 식을 도출 할 수 있었습니다.
사용할 수 없는 정사각형의 개수 = 가로 + 세로 - 1 (단, 가로와 세로가 서로소)
빨간 직사각형의 가로와 세로는 주어진 W와 H를 각각 최대공약수로 나눈 것이기에 서로소이며, 꼭지점 2개를 지나는 대각선은 빨간 직사각형의 가로만큼, 그리고 세로만큼 지나갑니다. 하지만 대각선이 시작되는 첫부분(노란색)은 서로 겹치기에 1을 빼서 중복으로 계산되는 부분을 차감해줍니다. 따라서 문제의 답은 직사각형의 넓이(W*H)에서 한 패턴에서 사용할 수 없는 정사각형의 개수(W/최대공약수(W,H)+H/최대공약수(W,H)-1)와 패턴반복횟수(최대공약수(W,H))의 곱을 차감해야 합니다.
answer = W x H - (W / gcd(W, H) + H / gcd(W, H) - 1) x gcd(W, H) = W x H - (W + H - gcd(W, H))
- 느낀점
오랜시간 고민 끝에 나온 코드가 너무 짧아서 허무한 느낌이 들었습니다. 이번 문제는 지난 문제들과는 다른 어려움을 느낄 수 있었습니다. java언어에서의 미숙함에서 나온 어려움이 아닌 단순한 수학적 사고능력이 부족해서 나온 어려움이라고 생각합니다. 하지만 굉장히 재밌었습니다.
