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

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

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

 

문제를 간단히 요약하면 

 

높이 h와 너비 w의 길이를 가진 직사각형에서 대각선으로 선을 긋는 다면 

살아남는 한변의 길이가 1인 정사각형의 개수는 몇개인가. 이다

 

 

 

당시 내 심정 : ??????????????????

기하학...인가?...

직선이 지금 너의 구역을 통과중이라고 어떻게 정사각형한테 알려주지??...

등등 머리를 1시간정도 썼지만.. 하드코딩으로 넘어가는것 같아 힌트를 하나만 봤다.

 

바로 최대공약수

 

 

아!!!

 

 

반복패턴이 나온다는건 캐치하였지만, 그 반복의 횟수에 대해서는 캐치하지 못했었다.

 

여기서 그 반복의 횟수가 바로 w와 h의 최대공약수라는 것.

사진은 12*8짜리라 최대공약수인 4회가 반복되는것이다.

 

 

이제 그렇다면 

저 축소된 문제에서 답을 구하는 것만 남았는데 

이것도 사실 풀이를 보고 왜 저 식이 나오게 되었는지 이해한것을 바탕으로 포스팅을 한다

 

세로

직선은 결국 세로로는 h/gcd(w,h)인 3칸을 지나게 되며

 

 

 

가로

가로로도   w/gcd(w,h)인 4칸을 지나게 된다.

 

 

 

이걸 마지막으로 식을 써보면

 

첫번째줄 마지막 1을 더하는 이유는 처음 정사각형 포함

 

이렇게 나온다.

 

 

 

 

이걸 다시 코딩으로 정리하면

이렇게 나타낸다.

 

answer와 temp의 타입이 long인 이유는

이거때문이다

자바에서 Integer는 4byte 데이터타입,  -2^31~2^31의 수만 표현이 가능하다

–2,147,483,648 ~ 2,147,483,647 의 수인데,

1억*1억이면 1해 라는 수가 나온다.....

 

그래서 8byte짜리 long을 쓰는것이다.

 

정답!

 

오늘도 나는 부족한 사람이란것을 또 느꼈고,

부족한 나의 지식이 누군가에게 도움이 되었기를 바라며

 

이만 빠잉!