멀쩡한 사각형

 

 

---

 

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

프로그래머스

 

---

문제 고민

공식

제거되는 상자 = X + Y - 두 수의 최소공배수

 

위 사진의 사각형을 보라

핑크색이 제거 될 상자이다 총 16개

X축한 칸마다 주황색으로 12개했다

Y축 한 칸마다 보라색으로  8개 했다

XY가 겹치는 부분은 연두색 별 4개

---

 

해결 코드

greatCommonFactor

 

public class 멀쩡한사각형 {

	public static void main(String[] args) {
		Solution solution = new Solution();
		int w = 8;
		int h = 12;
		long result = solution.solution(w, h);
		System.out.println(result);//80

	}

	static class Solution {
		public long solution(int w, int h) {
			// 지나가는 선 개수 w+h-최대공약수
			// 12~17 틀리는 이유 int*int 할 때 int 범위 벗어날 수 있어서 캐스팅
			return Math.max(((long) w * (long) h) - w - h + greatCommonFactor(w, h), 0);
		}

		private int greatCommonFactor(int w, int h) {
			while (h != 0) { // 최대공약수를 구할때까지
				int temp = h;//다음 계산을 위해 세팅, 나눠질 값
				int remainder = w % h;// 나머지

				// 다음 계산을 위한 세팅
				w = temp;//w사용이 끝나고 -> 다음 계산을 위해 세팅, 나눠질 값 세팅
				h = remainder;//다음 계산을 위해 세팅, 나머지를 나눌 값 세팅
			}

			return w;//나눠질 값 리턴.. 이때 h==0임
		}

	}// Solution class end

}// one class end

 

---

 

 

 

 

---

 

 

---