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

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

코딩테스트 연습 - 멀쩡한 사각형 | 프로그래머스

문제

• 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 SOLUTION을 완성해라

제한 사항

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

입출력의 예

• W = 8, H = 12, result = 80

풀이

직사각형의 각 변을 m,n이라고 할 떄 공식은 m+n-(m,n의 최대공약수) 입니다.

 

H, W 각 변의 크기를 비교하여 최대공약수의 값을 구할 준비를 한다.

	if (H > W) {
		big = H;
		small = W;
	} else {
		big = W;
		small = H;
	}

 

최대 공약수를 구하는 메서드 이다. a % b == 0 일 때는 b의 값이 최대 공약수가 된다.

아니면 재귀함수를 사용하여 a % b == 0 의 값을 찾아준다.  

  public static int gcd(int a, int b) {
		
	if (a % b == 0) {
		return b; 
	}	
       
	return gcd(b, a % b);
}

 

대각선이 닿지 않는 부분을 찾아야 하는 공식 이다.

answer = ((long)H * W) - (W + H - temp);

 

class Solution {
    
	public long solution(int W,int H) {
        
      	int big = 0, small = 0, temp = 0;
		long answer = 0;
		
		if (H > W) {
			big = H;
			small = W;
		} else {
			big = W;
			small = H;
		}
		
		temp = gcd(big, small);
        
     	answer = ((long)H * W) - (W + H - temp);
            
		return answer;
	}
    
    public static int gcd(int a, int b) {
		
		if (a % b == 0) {
			return b; 
		}	
        
		return gcd(b, a % b);
	}
}

참고[https://m.blog.naver.com/PostView.nhn?blogId=zzinuhelios&logNo=120024685950&proxyReferer=https%3A%2F%2Fwww.google.com%2F]