[Programmers] 멀쩡한 사각형

summer/winter coding(2019) 문제

문제

코딩테스트 연습

코딩테스트 연습

 

 

가로 길이가 W cm, 세로 길이가 H cm 인 직사각형 종이가 있고, 종이는 1cm X 1cm 의 격자칸이 있다.

종이를 왼쪽 위 꼭지점에서 오른쪽 아래 꼭지점으로 대각선을 그을 때,

종이에 남아있는 정사각형의 개수를 구하는 문제이다.

 

제한사항

• W, H : 1억 이하의 자연수

 

---

 

해결 방법

 

대각선에 대한 기울기와 접점으로 일차함수 식을 구해서 문제를 해결했다.

 

위의 그림과 같이,

왼쪽 아래를 기준으로 좌표를 정하고 대각선의 식을 구했다.

대각선을 지나는 사각형의 개수를 전체 개수에서 빼는 방법으로 식을 작성했다.

 

대각선을 지나는 것을 확인하기 위해서,

가로를 기준으로 세로 값을 구하고 그 값과 직전 가로에서의 세로 값을 뺐다.

 

예를 들자면, W가 4이고, H가 5일 때, 아래와 같은 값을 구할 수 있다.

 

x = 0일 때, y = 5이고,

x = 1일 때, y = 3.25이다.

가로가 0에서 1 사이에서 사각형은 5 - 3.25 = 1.75 만큼이고, 올림으로 2개를 제외해야 한다.

 

 

코드로 작성하면, 아래와 같다.

#include <iostream>

using namespace std;

long long solution(int w,int h) {
    long long answer = w * h;
    long long before, after;

    if (w == h) {
        return answer - w;
    }
    before = h;
    for (int i = 1; i <= w; i++){
        after = h - (h * i) / w;
        answer -= before - after;
        if (h * i % w) {
            answer -= 1;
        }
        before = after;
    }
    return answer;
}

 

이때, long long 은 실수가 아닌 정수 자료형으로 나눗셈의 값은 정수가 된다.

y = 3.25 이면, 실제 after 값은 3이 되므로 버림으로 처리된다.

따라서, 나머지 연산(%)으로 나머지 값이 있는 경우에는 1을 더 뺐다.

 

그러나 코드 제출 시에 오류가 발생하고, 테스트케이스 12 ~ 17번까지 실패한다.

 

이는 자료형때문이다!

 

W, H 값은 최대 1억으로 answer 변수를 선언하면서 두 값을 곱하는 연산을 해서 오류가 발생했다.

W와 H는 int 자료형으로 1억과 1억을 곱하면 자료형 범위를 넘어선다.

연산의 결과값이 long long 자료형에 저장되지만, 이미 연산 과정에서 범위를 넘어서서 오류가 발생했다.

이를 해결하기 위해서, W와 H 값을 long long 으로 변환한 후에 사용했다.

 

 

---

 

결과 코드

 

#include <iostream>

using namespace std;

long long solution(int w,int h) {
    long long x = static_cast<long long>(w);
    long long y = static_cast<long long>(h);
    long long answer = x * y;
    long long before, after;

    if (w == h) {
        return answer - x;
    }
    before = y;
    for (long long i = 1; i <= w; i++){
        after = y - (y * i) / x;
        answer -= before - after;
        if (y * i % x) {
            answer -= 1;
        }
        before = after;
    }
    return answer;
}

곱셈과 나눗셈의 순서에 따라 값이 달라질 수 있다!