[프로그래머스] 멀쩡한 사각형 / c++

https://programmers.co.kr/learn/courses/30/lessons/62048

코딩테스트 연습 - 멀쩡한 사각형

 

 

 

 

[ 코드 ]

 

using namespace std;

long long solution(int w,int h) {
    long long answer = 1;
    long long mark_n;
    long long division_n;
    long long new_w, new_h;
    long long sum = (long long)w * (long long)h;
    
    if(w>h) mark_n = h;
    else mark_n = w;
    
//    mark_n = (w>h) ? h : w; 한 줄 가능.
    
    for(int i=mark_n; i>0; i--){
        if(w%i==0 && h%i==0){
            division_n = i;
            break;
        }
    }
    
    new_w = w/division_n;
    new_h = h/division_n;
    
    answer = sum - division_n * (new_w + new_h - 1);
    
    return answer;
}

 

 

[ 접근 방법 ]

 

일단 이 문제를 풀기 위해선, 최대공약수가 무엇인지를 구해야한다.

 

1. 가로 세로 중 더 짧은 길이를 mark_n에 저장

2. for문에서 mark_n부터 수를 줄여나가며 가로, 세로를 나눴을 때 0으로 나눠떨어지는 가장 큰 수가 나오면 break;

3. 최대공약수로 나눈 가장 작은 사각형을 구함. ( 빨간 사각형 )

 

 

여기서 같은 수로 나누었을 때 0으로 나눠 떨어지는 수로

새로운 가장 작은 사각형의 가로 세로 길이를 구했기 때문에,

가로로 세도 division_n개

세로로 세도 division_n개

로 작은 사각형의 갯수가 나올 것이다.

 

그리고 여기서 막혔었는데,

작은 사각형 안의 살아남는 멀쩡한 사각형의 공식은

 

멀쩡한 사각형 = 작은 가로 + 작은 세로 - 1

 

이다.

 

따라서

 

answer = sum - division_n * (new_w + new_h - 1);

 

의 공식을 세울 수 있다!

 

 

 

 

 

 

 

[ 틀린 코드 ]

 

using namespace std;

long long solution(int w,int h) {
    long long answer = 1;
    long long mark_n;
    long long division_n;
    long long new_w, new_h;
    long long sum = (long long)w * (long long)h;
    
    if(w>h) mark_n = h;
    else mark_n = w;
    
//    mark_n = (w>h) ? h : w; 한 줄 가능.
    
    for(int i=0; i<mark_n; i++){
        if(w%i==0 && h%i==0 && division_n<i){
            division_n = i;
        }
    }
    
    new_w = w/division_n;
    new_h = h/division_n;
    
    answer = sum - division_n * (new_w * new_h - 1);
    
    return answer;
}

 

다른 부분은 크게 다르지 않고, for문에서 최대공약수를 구하는 부분을 큰 수부터 찾아가는 것이 문제가 되었다.

 

이 코드를 돌리게 되면,

 

 

signal: floating point exception (core dumped)

 

이 오류가 뜬다!

 

이 오류는 나누기를 할 때 변수/0이 있으면 발생한다.

 

한마디로 0으로 나누면 안된다는 뜻.

 

 

아마 division_n에서 0을 바로 받고

 

new_w = w/division_n;

new_h = h/division_n;

 

여기에서 문제가 난 것 같다.

 

 

 

[ 다른 사람의 코드 ]

 

#include<iostream>

using namespace std;

long long solution(int w, int h)
{
	int gcd;
	long long sum = (long long)w * (long long)h;
	
	for (int i = (w < h) ? w : h; i > 0; i--) { //최대 공약수 구하기
		if ((w % i == 0) && (h % i == 0)) { 
			gcd = i;
			break;
		}
	}
	return sum - gcd * ((w / gcd) + (h / gcd) - 1);
}

 

한번에 for문 안에서 더 짧은 길이를 구해서 적용하고,

return 에서 바로 공식을 써주고 가장 짧은 사각형의 가로 세로도 구해 대입했다.

 

짧아 보기 좋지만, 설명적으로는 부족할 수 있어 보인다.

 

 

 

※ 오늘의 교훈

초반에 공식을 구하는 데 애를 너무 먹었다. 수학적 사고 능력을 더 키울 필요성.

오류가 났을 경우 무슨 오류인지, 어디서 났을 지 찾아보며 배움.