[프로그래머스] 멀쩡한 사각형 C++ 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/62048?language=cpp 

프로그래머스

 

전체 코드

using namespace std;

long long solution(int w,int h) {
    long long answer = 0;
    
    for(int i=1;i<w;i++)
    {
        
        long long n = ((double)h * i)/w;
        answer+=n;
    }
    answer*=2;
    return answer;
}

 

일차함수를 통해 푸는 방법이 있다.

다들 최대공약수를 통해서 푸는것 같던데 내 스타일이 아니라... 일차함수를 통해 풀었다..

 

 이렇게 대각선을 일차함수로 보고 푸는것이다.

예제를 통해 예를 들어보자면

이 일차 함수를 통해 x가 1~(w-1)일때 그릴 수 있는 정사각형 개수를 세는것이다.

그리고 대칭으로 대각선 위에도 동일하게 정사각형 개수가 있을테니 최종적으로 *2를 해준것!

 

조금 이해를 돕기위해 x가 1 2 3일때를 예로 들어보겠다.

예제의 대각선은 y=(12/8)x 이다.

x가 1일때 y는 1.5가 나온다. 즉 x가 1일때 y는 1.5가 나오는것.

하지만 우리가 필요한것은 정사각형이므로 높이가 1인 정사각형 하나만 채울 수 있는것이다.

즉 y를 정수로 바꾼것이 정사각형으로 채울 수 있는 최대 높이이자 최대 개수인것 이다.

이렇게 정사각형 하나를 잘라낼 수 있는것이다~

 

이런식으로 x가 2일때 정사각형 3개를 오려낼 수 있는것이다.

 

x가 3일때 y는 4.5가 나온다 그럼 정사각형은 ? 4개가 최대로 자를 수 있는것이다.

 

이렇게 쭉 x는 1부터 w-1까지 y를 구해서 int형으로 바꿔버리면 자를 수 있는 정사각형의 개수가 나온다.

아래는 x가7일때 자를 수 있는 정사각형의 개수를 나타내며 10개를 자를 수 있다.

 

 

그래서 일차함수에 i를 넣어 나오는 값을 정수 n으로 바꿔 합산해서 곱하기2 해줄 계획이였다.

하지만 테스트케이스 6번이 자꾸 틀리는것이다. 이때 아래와 같은 코드를 작성했다.

long long n = ((double)h/w) * i;

그냥 함수에 i를 넣은것인데 틀리는것이다. 이게 찾아보니 아래와 같은 이유인것 같다.

 

"소수점을 가진 값의 계산이 조금 부정확합니다. 예를 들면 0.1 + 0.2 = 0.300000000000000000004 처럼 나오는데요. 이 말은 소수점을 가진 값을 계산을 할수록 더 부정확해진다는거죠. h/w를 나눠서 i를 곱하는것은 h/w라는 소수점을 가진 값에 어떤 값을 곱해서 또 소수점을 가진 값을 만드는 것입니다. 차라리 h에 i를 먼저 곱한뒤 w로 나눠보세요 그럼 계산이 더 정확해져서 통과합니다."

 

그래서 소수점의 계산을 최소화하기 위해

나누기를 나중에 해주니 통과하더라.

long long n = ((double)h * i)/w;