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

https://school.programmers.co.kr/learn/courses/30/lessons/62048

프로그래머스

---

풀이 과정

격자 칸 1cm*1cm로 이루어진 w cm, h cm의 직사각형을 대각선으로 찢을때 사용 가능한 1cm*1cm 사각형의 면적을 구하는 문제이다.

 

다른 사람들의 코드를 보면 w*h-(w+h-gcd(w,h)) 라는 식으로 많이 풀었던데 풀이가 와닿지 않아서 대각선을 일차 함수로 생각하여 해결하였다.

 

w = 8, h = 12일때 y = 3/2x 라는 직선 밑에 있으면서 직선과 겹치지 않은 사각형의 개수를 구한 뒤, 2배를 해주어 답을 구하였다.

 

파이썬으로 풀이시 시간초과가 발생하므로 파이썬으로 문제 풀이시에는 w*h-(w+h-gcd(w,h)) 라는 식으로 문제를 해결해야 한다.

 

---

소스 코드

using namespace std;

long long solution(int w, int h) {
    long long answer = 0;

    for (int i = 0; i < w; i++) {
        answer += int((double)h*i/w);
    }

    return 2 * answer;
}