이번 문제는 프로그래머스 Level 2 멀쩡한 사각형 입니다.
문제 설명
가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.
한줄로 요약하면!!
가로/세로 값이 해당 사이즈의 직사각형을 반절로 접었을 때, 그 대각선을 지나는 칸을 제외한 나머지 칸을 구하면 됩니다.
제한사항
W, H : 1억 이하의 자연수
입출력 예시
w = 8 , h = 12 일때, 전체 칸은 96칸 입니다.
그 직사각형의 대각선을 그립니다. 해당 대각선이 지나는 칸이 총 16칸이기 때문에 그 만큼을 제외한 80칸이 return 됩니다.
코드 작성 전, 생각 정리
- 파라미터가 int 타입인데, return 타입이 long이라 계산할 때 타입 변환하기
- 다른 값들 통해서 규칙성을 찾기
- 위의 사진을 보면, 총 4번의 동일한 패턴을 보인다.
여기서 4라는 숫자가 어떻게 나올 수 있을까?
예제에서 8과 12일 때, 4라는 숫자는 여러가지로 생각해볼 수 있지만 최대공약수로 추측할 수 있다. 그 외의 경우에도 고려해보면 공약수가 없는 경우를 제외하면 모든 경우에 최대공약수로 결과값을 구하면 원하는 값과 동일하다.
-
(2,3)일 때, 4개의 직사각형이 영향을 받음
-
(5,2)일 때, 6개의 직사각형이 영향을 받음
일반식으로 만들어보면!!
영향을 받는 직사각형의 수 = (너비) + (높이) - 1 이 되고,
결론적으로 전체 계산식을 작성하면
(너비) x (높이) - ((너비) + (높이) - 1) x (최대공약수)이 됩니다.
코드(자바)
class Solution {
public long solution(int w, int h) {
long answer = 1;
long big = gcd(w,h);
long weight = (long)w;
long height = (long)h;
answer = weight*height - ((weight/big)+(height/big)-1)*big;
return answer;
}
public static long gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return (long)a;
}
}
개인 소감
규칙성을 찾는데 시간이 걸렸다. 매번 코딩 테스트 문제만 풀이하면서는 '어떤 라이브러리의 어떤 메소드를 사용하면 좋을까?' 이런 고민들을 많이 했었다. 너무나도 많은 라이브러리에 메소드를 기억하기 어려워서 찾아서 공부하고, 찾아서 코드에 작성하는 형식이였다. 이번 문제는 다른 문제들과 다르게 오랜만에 라이브러리와 메소드를 고민하는 것보단 고등학교 시절로 돌아가 수학 문제를 풀던 때로 돌아간 기분이였다. 뭐든 안하면 잊어버리고 머리가 굳기 마련이다. 굳지 않고 말랑말랑한 상태 유지를 위해서 열심히 노력하자!!
