문제
멀쩡한 사각형 프로그래머스 level2
리뷰
가로 W, 세로 H가 1억 이하의 자연수로 들어오기 때문에, 변수들을 long long 형으로 처리해줘야 한다.
넓이를 구할 때 얘네를 곱셈을 하니까 int 표현 범위를 넘어설 수 있기 때문이다.
가로, 세로 비율에 따라서 사용불가한 종이의 개수가 일정하다.
최대공약수가 필요하겠다 싶어서 gcd 함수를 만들었다.
// 재귀 형태 GCD
long long gcd(long long a, long long b){
if(b == 0) return a;
else return gcd(b, a%b);
}
// 반복문 형태 GCD
int GCD(int a, int b){
int i = 1;
for(i = (a<b)? a:b; i > 0; i--){ // 작은 수를 i로 두고 시작
if( (a%i == 0 ) && (b%i == 0) ){ // 둘 다 나누어 떨어지는 숫자를 구하면 탈출 !
break;
}
}
return i;
}
너비 W를 gcd 로 나눈 길이와 높이 H를 gcd로 나눈 길이로 된 사각형에서 규칙성이 발견된다.
예를 들어, 가로 8, 세로 12 라면, 최대공약수 gcd가 4이다.
가로 2, 세로 3 사각형 단위로 종이가 총 6칸이다. 여기서 사용불가 종이가 4개씩 발생한다.
사용불가 종이가 가로2 + 세로3 - 1개 씩 발생한다. ( 4 == 2+3-1)
직사각형 종이의 가로 8, 세로12 에서도 최대공약수 만큼 사용불가 종이가 발생한다.
사용불가 16개 == 8 + 12 - 4
총 넓이 (W * H) 에서 16개를 빼면 답이 나온다.
이 때 W, H를 곱한 수가 int 표현범위를 초과할 수 있으니까 전부 long long 으로 처리한다.
코드
using namespace std;
long long gcd(long long a, long long b){
if(b == 0) return a;
else return gcd(b, a%b);
}
long long solution(int w,int h) {
long long answer = 1;
long long total =(long long)w * h; // 직사각형의 총 넓이
long long gcd_num = gcd((long long)w, (long long)h); // W, H의 GCD
answer = total - (w + h - gcd_num);
return answer;
}
처음 짰던 코드
using namespace std;
long long gcd(long long a, long long b){
if(b == 0) return a;
else return gcd(b, a%b);
}
long long solution(int w,int h) {
long long answer = 1;
long long total = (long long)w*h;
long long gcd_num = gcd((long long)w, (long long)h); // GCD
long long temp_w = (long long)w / gcd_num; // w를 GCD로 나눈 길이
long long temp_h = (long long)h / gcd_num; // h를 GCD로 나눈 길이
// 사용 불가 종이의 개수 == (temp_w + temp_h -1)
long long block_cnt = w / temp_w;
answer = total - (block_cnt * (temp_w + temp_h -1) );
return answer;
}