[C++] level2 멀쩡한 사각형 62048

📌멀쩡한 사각형

문제 설명
가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한사항
W, H : 1억 이하의 자연수
입출력 예

W = 8, H = 12일 때 return    80

입출력 예 설명
입출력 예 #1

가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

📌풀이

처음 문제를 보고, 뭐야 이게 level2야? 하면서 그냥 행별 또는 열별로 카운트 세서 전체에서 빼주면 되는거 아냐?라는 안일한 생각을 했다. 반성한다.
이 문제는 수학적 사고가 필요한 문제이다. 나같이 멍청하게 1차원적으로 문제를 푼다면 전원 테케 실패를 맛 볼 수있다. 아주 ... 매운 맛이다 ... ^6 ^...
여러 블로그를 참고해보니 접근법은 크게 2가지로 나뉘는 것 같았다.

주의사항 : 자료형 (long long 타입)

접근법 1 ) 일차함수, 올림, 대칭의 3가지 원리를 사용한 문제 풀이

특징

• 대각선을 기준으로 1x1 정사각형들이 대칭으로 포진되어 있다.
• 대각선 위쪽의 정사각형은 y값을 올림한 값부터 시작한다.

먼저 직선의 방정식을 이용하여 대각선을 기준으로 한 쪽 면(왼쪽 면)의 1x1 블록 크기를 더해준다.

for(int i = 1; i <= w; i++){ //x길이 만큼 돌음
    //1x1블록의 각 위치를 pos로 잡아
    double pos = ceil((long long)h * i / double(w));
    int block = h - pos;

    answer += block;
}

for문을 모두 돌았으면 한 쪽 면의 블록의 개수는 다 구한 상태이다. 대각선을 기준으로 대칭이므로 answer * 2를 해주면 전체 블록에서 대각선을 제외한 블록의 개수를 구할 수 있다.

answer * 2

접근법 2) 최대공약수를 사용한 문제 풀이

선을 그어보면 y값이 소수값을 가지지 않고, 정수 값을 가지는 경우를 볼 수 있음 (==일정 블록 크기를 가진 패턴)
해당 블록의 길이(x)는 w를 h와 w의 최대공약수로 나눈 길이고, y의 길이는 w와 h의 최대공약수로 나눈 길이다.

long long answer = 1;
int gcd = 0;
int start = w < h ? w : h; //더 작은 값을 start로 두고 최대공약수를 구함

    for (int i = start; i > 0; i--)
    {
        if ((w % i == 0) && (h % i) == 0)
        {
            gcd = i;
            break;
        }
    }

해당 블록에서 선이 지나가는 칸의 갯수는 (x길이 + y길이 - 1)임을 이용하여 전체 칸수 - 선이 지나가는 전체 칸수를 지워 대각선 제외 직사각형의 1x1 크기의 정사각형의 개수를 구할 수 있다.

long long all = (long long)w * (long long)h; //전체 길이

answer = all - gcd * ((w / gcd) + (h / gcd) - 1);

📌코드

내가 작성한 코드라고 보기 어렵기 때문에 코드 부분은 생략하고 해당 글을 작성하는 것으로 공부를 대체한다...
다시 풀어봐야지 꼭!

---

참고자료
https://sueaty.tistory.com/109 //접근법 1
https://minnnne.tistory.com/38 //접근법 2