[C++] 멀쩡한 사각형 (Lv.2)

문제 (level2, Summer/Winter Coding(2019)

문제 바로가기

---

풀이(나만의 풀이법, 최대공약수X)

 

정석적인 풀이는 최대공약수를 이용하는 것인데, 저는 저만의 방식으로 풀었습니다.

 

using namespace std;

int check(double x, double y, double a, double b)
{
    if(a*x+b-y<0)
        return 1;
    else if(a*x+b-y==0)
        return 0;
    else 
        return -1;
    
}

long long solution(int w,int h) {
    //y=ax+b
    double a,b;
    a=-(double)h/(double)w;
    b=(double)h;
    long long aws=0;
    long long y=h-1;
    
        for(long long x=1; x<=w; x++)
        {
            int position; // 1은 선분보다 위, 0은 겹침 , -1은 아래
            position=check(x,y,a,b);
            
            aws++;       
            if(position==1)
            {
                while(y>=0 && check(x,y,a,b)==position)
                {
                    y--;
                    if(check(x,y,a,b)!=position)
                    {
                        aws++;
                        if(check(x,y,a,b)==0)
                            y--;
                        break;
                    }
                    else
                        aws++;
                }
            }
            else if(position==0)
            {
                y--;
            }

        }
        return (long long)w*h-aws;
    
}

먼저 사각형에 대각선을 그은것을 y=ax+b 형태로 생각합니다.

 

그러면 a=-h/w; b=h; 가 나오게 됩니다.

 

 

 

 

그리고 저는 위 그림에서 빨간점을 찍은 부분들을 직선의 방정식에 대입해줍니다.

 

 

 

저는 열을 기준으로 검사했습니다. (첫번째 열은 위 그림에서 주황색 영역)

 

대각선에 빨간점을 대입했을때 대각선 위라면 position=1,

대각선과 겹친다면 position=0,

대각선 아래라면 position=-1

로 처리해줬습니다.

 

만약 위처럼 첫번째 열 검사때,

첫번째 빨간점의 position이 1이라면 

그 아래 빨간점을 검사해줍니다. 

 

이때, 이 검사한 빨간점이 대각선 위가 아니라,

겹친다면==>다음에 검사할 y좌표값을 -1해주고 다음 열 검사(x좌표값+1)로 넘어감.

아래라면==>y좌표값은 건드리지않고 다음 열 검사(x좌표값+1)로 넘어감.

 

 

만약 첫번째 열 검사때

첫번째 빨간색의 position이 0이라면

정사각형 모양이기때문에 y--해주고 다음 열 검사(x좌표값+1)로 넘어갑니다.

 

 

만약 첫번째 열 검사때

첫번째 빨간색의 position이 -1이라면

그냥 바로 다음 열 검사로 넘어갑니다(x좌표값+1만 해주고 y좌표값은 바꾸지않음)

 

 

 

그렇게 끝까지 검사한 결과로 나오는 것은 대각선에 걸치는 칸의 갯수입니다.

 

요구하는 답은 그 나머지 칸들의 갯수이기때문에 전체 칸수에서 빼준값을 return해줍니다. 

 

 

 

 

 

 

 

 

위 알고리즘은 로직상에 문제는 없지만 숫자가 커질때 소수점 부정확함문제로 코드를 아래처럼 살짝 바꿔줘야 완벽하게 통과하게됩니다.

using namespace std;

int check(double x, double y, double w,double h, double b)
{
    if(-h*x/w+b-y<0)
        return 1;
    else if(-h*x/w+b-y==0)
        return 0;
    else 
        return -1;
    
}

long long solution(int w,int h) {
    //y=ax+b
    double b;
    b=(double)h;
    long long aws=0;
    long long y=h-1;
    
        for(long long x=1; x<=w; x++)
        {
            int position; // 1은 선분보다 위, 0은 겹침 , -1은 아래
            position=check(x,y,w,h,b);
            
            aws++;       
            if(position==1)
            {
                while(y>=0 && check(x,y,w,h,b)==position)
                {
                    y--;
                    if(check(x,y,w,h,b)!=position)
                    {
                        aws++;
                        if(check(x,y,w,h,b)==0)
                            y--;
                        break;
                    }
                    else
                        aws++;
                }
            }
            else if(position==0)
            {
                y--;
            }

        }
        return (long long)w*h-aws;
    
}

바뀐점은 y=ax+b에서 

원래는 a (=h/w)를 구하고 check()함수 내에서 a*x (=h/w*x)를 해줬는데

이때 h/w가 먼저 계산된뒤에 *x 를 했기에 부정확해지는 문제가 발생했습니다.

 

따라서 a를 따로 구하지 않고 h,w를 check()함수의 인자로 받아서 

a*x (=h/w*x와 같음) 를 h*x/w 로 연산 순서만 바꿔서 정확도를 높였습니다.

 

 

---

풀이(최대공약수 사용)

다른 분 블로그 풀이 링크

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

이분 블로그가 설명을 깔끔하게 잘 하신 것 같아서 링크만 걸어두겠습니다.

(핵심:W*H의 사각형을 대각선으로 잘랐을때 망가지게되는 사각형을 구하는 최종 공식 : [ W+H-최대공약수 ])