[Java][프로그래머스-코딩테스트 level2] 멀쩡한 사각형

o 요구사항

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 주어진다.

대각선 꼭지점 2개를 잇는 방향으로 잘렸을때 1cm의 온전한 사각형 개수를 구하기

 

o 코드진행

1. 길이가 1씩 증가할 때 온전한 사각형은?

가로 width, 세로 height의 직각삼각형을 그릴 수 있다. 여기서 아래쪽 삼각형을 보자.

이 삼각형은 가로가 1씩 증가할 때마다 세로는 얼마나 감소할까. 정답은 height/width 길이만큼 감소하게 된다.

즉, 가로가 width를 width로 나눈 1(=width/width)씩 증가할때 세로는 height/width 만큼 길이가 줄어든다.

가로가 n만큼 이동했을때의 가로세로 1cm온전한 사각형의 개수는 세로길이에서 height/width를 n번 뺀 계산한 값에서 소수점을 버린 값과 일치하게 된다.

위 그림에서 빨간색으로 표시된 길이만큼 가능하다. (그림이 형편없네요..)

2. 두번째 삼각형 안에 있는 사각형 개수는?

아래쪽 삼각형의 1cm 사각형 개수를 구했으니 위쪽 삼각형 안에 있는 것도 구해야 한다.

위 식을 다시 반복할 필요없다. 아래쪽과 위쪽 삼각형은 정확히 대칭이므로 1cm사각형 개수도 정확히 일치한다.

곱하기 2하면 된다.

 

o 코드설계

위에서 언급한대로 세로는 height/width 만큼 가로가 진행됨에 따라 감소하게 된다.

가로가 n만큼 진행했을 때 세로길이를 식으로 표현하면 다음과 같다.

double 세로길이with소수점 = height - height/width*n

 

사각형은 소수점을 버린 세로길이만큼 가능하다. 

Java - Math 클래스의 floor(double값) 메소드를 사용하면 내림값을 구할 수 있다. 

int 세로길이(소수점버림) = Math.floor(세로길이with소수점);

 

반복문을 이용해 width만큼 진행할 때 온전한 1cm사각형을 구한다..(1)

모든 (1) 값의 누적값*2 가 정답이다.

o 완성코드

class Solution {
    public long solution(int w, int h) {
        long sum = 0;
        //Math.floor() 는 인자값으로 double 값을 받기 때문에 double로 선언했다.
        double width = w;
        double height = h;        
        double length_nature = 0;
        //가로길이는 1부터 W까지이므로 반복문 인자값을 조정해준다
        for(int i=1; i<=w; i++) {        	
        	length_nature = Math.floor(height - height/width*i);
        	sum += length_nature;
        }
        //위아래 삼각형이 대칭이므로 *2를 한다
        return sum*2;
    }
}