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

문제내용

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

코딩테스트 연습 - 멀쩡한 사각형

 

간단하게 1*1격자 로 이루어진 N*M 행렬이 있는데 왼쪽 위 꼭지점부터 오른쪽 아래 꼭지점까지 선이 이어져 있을때,

N*M 행렬에서 선이 지나치지 않은 1*1격자의 개수를 구하는 문제이다.

 

문제 입출력 예시는

가로길이(w) = 8

세로길이(h) = 12 일때

return 값 = 80 이다.

 

---

문제 접근 방법

문제 내용은 매우 간단하지만 w와 h에 따라 return값이 달라지기 때문에 규칙을 찾아내야한다.

 

처음 문제를 접했을때 맨땅에 헤딩하는 맘으로 피타고라스를 이용해 규칙을 찾으려고 하다가 도저히 안돼서 처음 부터 다시 생각했다.

 

일단 문제에서 사용할수 없게된 정사각형이 규칙적인 모양을 하고 있는다는걸 보고 모양의 개수를 셌을 때 4가 나왔다.

그리고 4를 어떻게 사용할수 있을까 봤는데 4는 가로길이(w)와 세로길이(h)의 최대공약수 라는걸 됐다.

 

그래서 사용가능한 정사각형 개수는

w*h - (한 덩어리당 사용 불가능한 정사각형 개수)*최대공약수

가 된다.

 

그리고 나는 한 덩어리당 사용 불가능한 정사각형 개수를

((w/최대공약수) * (h/최대공약수)) - 2 라고 생각했는데 이렇게 하니깐 틀렸다고 나온다.

 

그래서 사람들이 푼걸 봤는데 사람들은

한 덩어리당 사용 불가능한 정사각형 개수를

((w/최대공약수) + (h/최대공약수)) - 1 로 사용해 풀어냈다.

 

 

 

한마디로

w*h - (한 덩어리당 사용 불가능한 정사각형 개수)*최대공약수 ,

((w/최대공약수) + (h/최대공약수)) - 1,

최대공약수를 구하는 방법.

이렇게 세개의 방식을 찾아내면 풀리는 문제이다.

 

그리고 참고로 사람들이 w와 h는 1억이하의 자연순데 int형으로 담을수 있음에도 불구하고

계산과정에서 long으로 바꿔준다. 이유는 내 추측이지만

w와 h가 int형 최대값에 가깝게 정해졌을경우 w*h같은 계산에서 에러가 발생하기 때문이 아닐까 추측해본다

 

 

---

풀이

	public static long solution(int w, int h) {
		long answer = 0;
		int gcd = gcdMethod(w,h);//최대공약수
		answer = (long)w*(long)h - ((long)w/gcd + (long)h/gcd - 1)*gcd;
		
		return answer;
	}
	
	public static int gcdMethod(int a, int b) { //최대공약수 구하는 함수
		if(a%b==0) {
			return b;
		}
		return gcdMethod(b, a%b);
	}

 

 

---

마치며

문제 자체는 어려운 문제가 아니였지만

첫번째로 규칙을 찾아내는데 어려움을 겪었고

두번째로 규칙을 찾아낸뒤 구현하는데 시간이 소요됐던 문제이다.

 

문제 접근을 이렇게 나처럼 때려맞추는 식(감?)으로 접근하는게 맞는지는 모르겠지만.. 누가 알려준적이 없어서 나는 지금 이렇게 밖에 할수가 없다..ㅠㅠ 여튼 이번기회에 최대공약수를 구하는 알고리즘(유클리드 호제법)에 대해 공부 할수 있었다.