🎯문제
가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.
제한사항
- W, H : 1억 이하의 자연수
입출력 예
| W | H | result |
|---|---|---|
| 8 | 12 | 80 |
입출력 예 설명
입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.
✏️풀이
코드
class Solution {
// 유클리드 호제법
// 최대공약수를 구하는 메서드
public int gcd(int a, int b) {
if(b == 0) return a;
return gcd(b, a % b);
}
public long solution(int w, int h) {
// 가로, 세로 길이의 최대공약수를 구해줌
long temp = gcd(w, h);
// 전체 정사각형 개수 - (대각선을 지나는 사각형의 개수) * 반복횟수
return ((long)w * h) - (((w / temp) + (h / temp) - 1) * temp);
}
}설명
유클리드 호제법을 사용하고, 규칙을 찾아 진행하였다.
gcd 메서드는 유클리드 호제법을 사용하여 최대공약수를 구하는 메서드이다. 매개변수로 값을 2개를 받고 뒤에 있는 값이 0이라면 a가 두 수의 최대공약수가 되는 방식이다.
예를 들어, 48과 18이라는 값이 들어갔다고 하면
(48, 18)
18 != 0 이므로 gcd(18, 48 % 18) 재귀 호출
-> (18, 12)
12 != 0 이므로 gcd(12, 18 % 12) 재귀 호출
-> (12, 6)
6 != 0 이므로 gcd(6, 12 % 6) 재귀 호출
-> (6, 0)
0 == 0 이므로 6을 반환
즉 48과 18의 최대공약수는 6이 되는 것이다.
주어진 가로, 세로 길이의 최대공약수를 gcd 메서드를 사용해서 구해준다. 이후 수식을 계산해주면 되는데, 이 수식은 전체 정사각형의 개수 - (대각선을 지나는 사각형의 개수) * 반복횟수이다.
입력 예시를 가지고 설명을 해보자면,
w = 8, h = 12이다. 이때 전체 정사각형의 개수는 96이다.
그리고 대각선을 지나는 사각형의 개수를 구해주어야 하는데, 위의 입출력 예1번의 그림처럼 일정하게 나타나는 것을 알 수 있다.
저 대각선을 지나는 한 부분의 가로 길이는 w / 최대공약수, 세로 길이는 h / 최대공약수인 2, 3이 된다. 따라서 w / temp, h / temp는 대각선이 지나는 반복되는 가로, 세로길이가 되는 것이다.
이때 제거해야하는 부분은 가로길이 + 세로길이 - 1이다. 계속 예를 들어서 설명해보면 제거되어야 하는 정사각형의 개수는 4개이고, 이는 가로길이 + 세로길이 - 1 이라는 수식이 나온다. 당연히 위의 예시 뿐만 아니라 다른 값들을 그려본 뒤에 구해봐도 동일한 결과가 나온다.
해당 부분이 반복되는 횟수 역시 최대공약수이다.
따라서 제거해야하는 정사각형의 개수를 구하는 수식은 ((w / temp) + (h / temp) - 1) * temp가 되는 것이다.
위의 수식을 계산한 값을 반환하면 문제를 해결할 수 있다!
💡느낀 점
규칙을 직접 찾아서 해결하는 문제였는데, 입출력 예시가 하나밖에 없어서 다른 예시들을 생각해보면서 규칙을 찾느라 고민을 많이 했던 것 같다. 테스트 케이스를 생각해내는 것도 코테를 준비할 때 많은 도움이 되는 것을 알기 때문에, 열심히 생각해냈다. 하지만 케이스를 보고 규칙을 만들어내는 부분이 매우 어려웠고, 시간이 좀 걸렸던 것 같다. 다시 한 번 수학적 지능의 중요성을 알 수 있었다..
링크
