[프로그래머스] 멀쩡한 사각형 (Java)

프로그래머스 Level 2 멀쩡한 사각형 (자바)

 

 

출처

 

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

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

 

 

문제

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

 

 

 

제한사항

• W, H : 1억 이하의 자연수

 

 

 

입출력 예

입출력 예1

 

입출력 예 설명

가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

예시

 

 

 

 

걸린 시간

1시간이 조금 넘었다.. 오랜만에 풀어봤는데 하필 수학적 개념을 요하는 문제였다..

 

 

 

접근 방법

직사각형이 있다면 대각선으로 가로질렀을 때 선과 접하는 부분을 제외한 사용 가능한 부분의 개수를 구해야 한다.

 

먼저 자료형에 대해 생각해야 한다.

반환해야 하는 자료형은 long인데 매개변수는 모두 int로 주어졌다.

연산을 하는 과정에서 w와 h가 계속 필요한데 그때마다 캐스팅이 불편하니 처음부터 형변환을 시켜주었다.

 

이후에, 예시 그림을 보면 8(가로), 12(세로)를 최대공약수로 나누었을 때 (2,3)이 나온다.

(2,3)을 계속 +1씩 곱해나가보면 (4,6), (6,8), (8,12)이다. 이는 선과 만나는 좌표다.

 

그래서 최대공약수가 1인 (2,3)부터 보면 총 6개 박스에서 4개가 사용 불가능이다.

2(가로) + 3(세로) - 1(최대공약수) = 4(사용 불가능 박스 개수) 가 나온다. 확실하지 않아 (4,6)도 보겠다.

최대공약수 1

 

아래 그림을 보면 규칙적으로 진행된다는 것을 알 수 있다.

위 수식을 그대로 적용시켜보자.

4(가로) + 6(세로) - 2(최대공약수) = 8(사용 불가능 박스 개수) 가 정확히 나온다.

최대공약수 2

 

위 수식을 코드로 적용하면 w * h - (w + h - 최대공약수)이다.

 

수식 다음으로 최대공약수구하는 방법이 어려웠는데 작은 값으로 큰 값을 나눠주면서 값을 바꿔나가다 보면 최대공약수를 구할 수 있다. 최대공약수를 구하는 메소드를 따로 빼서 연산에 더해주었다.

 

 

내 코드

import java.util.*;

class Solution {
    public long solution(int w, int h) {
        long answer = 1;
        
        //가로 : W
        //세로 : H
        //직각삼각형 2개로 나누어짐
        //사용할 수 있는 정사각형 개수를 구해라?
        
        //전체 개수에서 사용 불가능한 사각형을 빼자
        //불가능한 사각형 : w + h - 최대공약수
        //ex) 2*3인(최대공약수 1인) 경우 사용 불가능한 사각형이 2+3-1(최대공약수) = 4로 구해진다.
        
        Long width = Long.valueOf(w);
        Long height = Long.valueOf(h);
        
        answer = width*height - (width + height - getGreatestNum(width, height));
        
        return answer;
    }
    
    long getGreatestNum(long width, long height) {
        
        //작은값으로 큰값을 나누기 위해 구분하기
        long small = height;
        long big = width;
        if (width < height) {
            big = height;
            small = width;
        }
        
        long temp = 0;
        while (small > 0) {
            temp = big % small;//나누기
            
            big = small;//8, 4
            small = temp;//4, 0
        }
        
        return (big);
    }//getGreatestNum
}

 

 

 

 

고려할 점

1. 최대공약수를 생각할 것

2. 그림을 보면서 어떤 규칙이 있는지 찾아볼 것