프로그래머스[Lv.2] - 멀쩡한 사각형

문제 설명

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

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

프로그래머스

---

 

 

 

 

 

 

제한 사항

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

---

 

 

 

 

 

 

풀이

그래프를 그려 문제를 풀면 된다.

그래프의 식을 만들어 x값을 대입하면 y값이 나오는데 이를 내림한 값이 멀쩡한 사각형의 개수이다.

이때, 내림을 하지 않고 int로 형변환을 한다면 자동으로 내림 연산을 하게되기 때문에 이를 이용하면 된다.

그래프의 식은 다음과 같다.

$y = -(H/W)x + H$

위의 예제와 같이 H:12, W:8인 상황에서 x에 1을 대입한다면, $y = -1.5 * 1 + 12$가 된다.

따라서, y의 값은 10.5인데 이를 int로 형변환하게 되면 10이다.

즉, 정확한 y값은 10.5인데 우리가 구해야 하는 값은 그보다 낮은 정수의 개수이므로 조건과 완벽히 일치한다.

---

 

 

 

 

 

전체 코드

#include <iostream>

using namespace std;

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

---