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

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

프로그래머스

 

문제 설명

 

길이가 W, 세로 길이가 H인 직사각형 종이가 있습니다.

종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1x1 크기입니다.

 

누군가 이 종이를 대각선 꼭짓점  2개를 잇는 방향으로 잘라 놓았습니다. 

그러므로 현재 직사각형 종이는 크기가 같은 직각 삼각형 2개로 나눠진 상태입니다.

이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1x1로 잘라 사용할 수 있는 만큼 사용하기로 하였습니다.

가로의 길이 W, 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구해주세요.

---

💡 아이디어

위의 예시 사진을 보면 잘라진 선을 직선 그래프 같다고 보았고,

x좌표가 0~W까지 직선 그래프보다 작은 y좌표까지를 , 정사각형의 개수라고 파악하고 문제를 풀었습니다.

 

📖 풀이과정

1. 우리가 구하려는 직선의 방정식을 y=ax+b라고 가정합니다.

주어진 W는 x절편, H는 y절편이기 때문에 a, b를 구해줍니다.

( * 주의해야 할 점은 기울기 a는 정수가 아니기 때문에 계산할 때 주의해야 합니다.)

x절편: y좌표가 0인 지점의 x좌표

y절편: x좌표가 0인 지점의 y좌표

 

2. x좌표를 1부터 w까지 y좌표를 구해 그보다 작은 정수(정사각형의 개수)를 answer에 더해줍니다.

기울기가 내려가는 함수이기 때문에 x=0~1인 정사각형은 x=1에서 영향을 받습니다.

3. 2번 과정에서 구한 정사각형의 개수는 직선그래프 아래에 해당하는 정사각형의 개수이므로, 

구한 개수의 2배를 해서 return 합니다.

 

크기가 같은 직각 삼각형으로 나눠졌기 때문에 한 번 더 계산할 필요 없이 2배 해주면 됩니다.

---

전체 코드

class Solution {
    public long solution(int w, int h) {
        long answer = 0;
        
        // y=ax+b 방정식 구하기
        double b=h;
        double a=(-h)/(double)w;
        
        //종이는 무조건 왼쪽위 에서 오른쪽 아래 끝으로 잘린다고 가정하면
        //기울기가 작아질 수 밖에 없기 때문에 x=0~1인 종이는 x=1일 때를 기준으로 생각한다.
        for(int x=1;x<=w;x++){
            answer+=(long)(a*x+b);//잘린 직각 삼각형의 왼쪽 아래 부분만 세어준다.
        }
        return answer*2;
    }
}