21. (TWOK/ALGORITHM) [Java] 멀쩡한 사각형 - 최대 공약수 , 최소 공배수

---

[환경 설정 및 설명]

​

언 어 : Java

​

설 명 : 멀쩡한 사각형 - 최대 공약수 , 최소 공배수

 

---

[소스 코드]

 

package ex5;

public class MainActivity23 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("[Program Start]");
		System.out.println("");
		
		/**
		 * [멀쩡한 사각형]
		 * 1. 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이에서, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 
		 *    그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다
		 * 2. 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요
		 * 3. 입출력 예시 : 
		 *    W (가로) : 8
		 *    H (세로) : 12
		 *    result : 80 (8*12 = 96에서 16 값을 뺀다)
		 *    
		 * 4. 입출력 예시 : 
		 *    W (가로) : 6
		 *    H (세로) : 9
		 *    result : 42 (6*9 = 54에서 12 값을 뺀다)   
		 * 5. 프로그래머스 사이트 : https://programmers.co.kr/learn/courses/30/lessons/62048   
		 * */
		
		// 초기 가로, 세로 변수 선언 실시
		int width = 8;
		int height = 12;
		
		// 결과 출력 메소드 호출 실시
		System.out.println("결과 : " + solution(width, height));
		
	}// 메인 종료
	
	public static long solution(int w, int h) {
		// 결과 값을 반환할 변수 선언 실시
		long result = 0;
		
		
		// 인풋으로 들어온 데이터 확인 실시
		System.out.println("width : " + w);
		System.out.println("height : " + h);
		System.out.println("");
		
		
		// result 반환 값에 먼저 가로*세로 연산 결과를 삽입
		result = w*h;
		
		
		/**
		 * [그림 참고해서 공식 구하기 실시]
		 * 1. height [1칸] 행 : 인풋으로 들어온 w 길이이며, 1부터 시작, 간격 차이가 2씩 커진다
		 * 2. height [2칸] 행 : 2부터 시작, 간격 차이가 3씩 증가한다
		 * 
		 * 3. 그림 표시 [가로 8 / 세로 12] : 최대 공약수 4 + 최소 공배수 24 = 28 - 12(높이) = [16]
		 * ================================= 
		 * 1   3   4    6   7     9   10     12
		 *   2        5         8         11  
		 * =================================
		 * 
		 * 4. 그림 표시 [가로 6 / 세로 9] : 최대 공약수 3 + 최소 공배수 18 = 21 - 9(높이) = [12]
		 * =================================  
		 * 1   3   4   6   7    9 
		 *   2       5       8     
		 * ================================= 
		 * */
		
		
		/* [최대 공약수 및 최소 공배수 설 명]
		 * 1. 최소공배수 - 공배수 중에서 가장 작은 정수입니다
		 * 2. 최대공약수 - 공약수 중에서 가장 큰 수입니다
		 * 3. 약수 - 약수는 어떤 수를 0으로 나누어 떨어지게 하는 수입니다
		 * 4. && 논리연산자 : 모든 조건이 true를 만족해야합니다
		 */	
				
		
		// 최대 공약수 및 최소 공배수 구하기 실시 
		int gcd = 0; // 최대 공약수
		int lcm = 0; // 최소 공배수
		int i = 1; // 약수 구하기 1부터 시작
		
		while(i<=w && i<=h){
			if(w%i==0 && h%i==0) { //두수가 모두 0으로 나누어떨어지는 경우
				gcd=i; //최대공약수에 i값을 대입한다
			}				
			i++; //i값을 증가시켜 최대 공약수값을 찾기위해 다시 while 반복문을 수행한다
		}
				
		lcm=(w*h)/gcd; //최소 공배수 구하는 식입니다
				
		System.out.println("최소 공배수 : " + lcm); 
		System.out.println("최대 공약수 : " + gcd);
		System.out.println("");
		
		// 결과 반환 실시 ((가로*세로) - (최대공약수+최소공배수-높이))
		return result - (gcd+lcm-h);		
	}

}// 클래스 종료

---

[참고 사이트]

​

https://kkh0977.tistory.com/1033

215. (java/자바) 알고리즘 : 멀쩡한 사각형 - 최대 공약수 , 최소 공배수

---