💨 문제 설명
가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다.
종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다.
이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다.
그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다.
새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.🚘 제한사항
- W, H : 1억 이하의 자연수
🍝 풀이
이 문제의 가장 중요하게 봐야할 키워드는 대각선을 구하는 방법과 최대공약수를 구하는 것이다.
먼저 문제를 해결하기 위해 고민하면서 최대공약수번 반복된다는 것을 발견하였다.
하지만 도대체 어떠한 규칙이 반복되는지 이해하기 어려웠다.
여러 풀이들을 봐도 이해가 안되었는데 그림으로 그려보며 확인하니 이해를 할 수 있었다.
먼저 이해하기 쉽게 왼쪽 모서리에서 오른쪽 모서리로 가는 경로를 찾기 위한 예시를 보자.
예시는 w = 3, h = 5인 최대공약수가 1인 경우이다.
▼ 3 x 5인 사각형
위의 그림은 왼쪽 모서리에서 오른쪽 모서리로 가기 위한 경로 중 하나이다.
이 경로는 아래와 같이도 표현할 수 있다.
y축으로 5칸, x축으로 3칸을 이동했다고 볼 수 있는데, 즉 w와 h의 크기만큼 이동을 한 것으로 볼 수 있다.
모든 경로에서 우리는 한 칸을 가로지를 수 있는 것이 아니기 때문에 총 7칸을 이동해야만 하는데 이때 왼쪽 아래 모서리와 같이 x축과 y축에서 중복되는 경우가 생긴다.
이는 모든 경우에서 x와 y축에서 중복되는 경우가 생긴다는 것을 알 수 있다.
위처럼 대각선 경로를 본 경우도 동일하다. 처음 시작하는 시작칸에서 중복이 발생하게 된다.
이러한 규칙을 보았을 때 최대공약수가 1인 경우(서로소인경우)의 대각선 경로의 크기는 (w + h) - 1 과 같이 표현할 수 있다.
그렇다면 최대공약수가 1보다 큰 경우는 어떻게 표현할 수 있을까?
▼ 9 x 15인 사각형
위의 예시를 3배 한 경우이다.
w = 9, h = 15의 최대공약수는 3이기 때문의 위의 3 x 5의 예시의 경우가 3번 반복된다고 볼 수 있기 때문에 대각선 경로의 크기는 (w + h) - 3 임을 알 수 있다.
위의 두 예시의 결과를 수식화 하면 대각선 경로의 크기, 즉 문제에서는 사용할 수 없는 정사각형의 갯수는 (w + h) - 최대공약수개 라고 할 수 있다.
결과적으로 이 문제는 전체 가능한 정사각형(사용할 수 있는)에서 사용할 수 없는 정사각형의 수를 제외하면 되는 것 이다.
최대공약수 구하기
이 문제의 핵심인 최대공약수 구하는 방법으로 유클리드 알고리즘을 사용하였다.
유클리드 알고리즘의 원리
- 두 수 a, b가 있다.
- a를 b로 나눈 나머지 n이 있다.
- n = 0이 될 때 b의 값이 최대 공약수가 된다.
이 알고리즘은 일반 반복문과 재귀함수를 사용할 수 있다.
나는 재귀함수를 통해 구현하였다.
🎇 코드
#include <iostream>
using namespace std;
int ckComprime(int x, int y);
long long solGCD(int x, int y);
long long solution(int w,int h) {
long long answer = 1, GCD = 1;
long long longW = (long long)w, longH = (long long)h;
GCD = solGCD(w, h);
answer = longW * longH - (longH + longW - GCD);
return answer;
}
long long solGCD(int x, int y) {
if (y == 0) return (long long)x;
return solGCD(y, x % y);
}😡 어려웠던 점
1. 사용할 수 없는 정사각형의 갯수 구하기(서로소인 경우)
→ 최대공약수를 사용해야 한다는 것은 알았지만 사용할 수 없는 정사각형의 수를 찾아내는것이 쉽지 않았다.
2. 유클리드 알고리즘
→ 유클리드 알고리즘을 구현한 적이 있었음에도 불구하고 서로소를 잘못하는 등 어렵게 생각하여 구현하는데 오래걸렸다.
3. 자료형
→ long long 형태로 되어있음에도 불구하고 마지막 answer에서 w, h를 long long으로 변환해주지 않아 자료형 에러를 겪게 되었다.
