[프로그래머스/JS] 멀쩡한 사각형 풀이

 

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

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

 

 

 

​

이것도 레벨 2여서 풀었는데

뭔가 공식만 잘 구하면 코딩자체는 쉬운문제

코딩문제라기보다 수학문제 .. ?

ㅋㅋㅋㅋ그래서..약간 횡설수설했다

간축한게 있고 자세~~하게 설명한 버전도 있다

풀이도 아래에 달아두었음!!

​

​

​

​

🍋 간축형 코드 답안

function solution(w, h) {
    //1. 최대공약수 구하기
    var gcd = 1;
    for(var i=2; i<=Math.min(w, h); i++){
        if(w % i === 0 && h % i ===0){
            gcd = i;
        }
    }

    //2. 정사각형 개수에서 못쓰는 정사각형 개수 빼기
    var answer = w * h - (w + h - gcd);
    
    return answer;
}

 

 

🍋 설명형 코드 답안

function solution(w, h) {
    //1. 최대공약수 구하기
    var gcd = 1;
    for(var i=2; i<=Math.min(w, h); i++){
        if(w % i === 0 && h % i ===0){
            gcd = i;
        }
    }

    //2. 최대공약수로 가로, 세로를 나눈 값으로 가장 작은 단위의 사각형 구하기
    var minW = w / gcd;
    var minH = h / gcd;

    //3. 가장 작은 단위의 사각형에 대각선을 그렸을 때 사용하지 못하는 정사각형 개수 구하기
    var pieceCnt = minW + minH - 1;

    //4. 가장 작은 단위의 사각형이 대각선으로 반복되는 만큼 곱해주기
    var allCnt = pieceCnt * gcd;

    //5. 전체 정사각형의 개수에서 allCnt를 빼주기
    var answer = w * h - allCnt;

    return answer;
}

설명형 코드는 위에 코드가 이해가 되지않을때 흐름, 원리를 파악하기 위해 읽어보기 좋다

​

​

​

 

​

🍋 풀이 의도

예제로 주어진 8, 12에 대한 그림이 있었는데 아래처럼 2, 3의 사각형이 반복된다는 것이 딱 눈에 보였다

​

그래서 먼저 반복되는 가장 작은 직사각형을 구해보자 라는 마음으로

가로 세로의 최대공약수를 구했는데 8과 12의 경우 4였다!

즉, 가로 세로 4개의 반복이 이루어질 수 있다는 것이기에

가작 작은 직사각형은 8/4 =2, 12/4=3 ➡ 2, 3의 사각형 이라는 것을 구할 수 있었다

 

그렇다면 2, 3의 사각형을 대각선으로 그리면 4개의 정사각형에 대각선이 표시되는데

이 4라는 숫자는 어떻게 구할까?

이것은 예시를 많이 만들어서 규칙을 찾아보면 되는데

 

2,3 = 4
2,4 = 5
2,5 = 6
3,4 = 6
3,5 = 7

 

규칙이 보인다 !!! 2 + 3 - 1 = 4

w + h - 1 이라는 공식을 구할 수 있다

 

그러면~~~ 다시 위로 돌아와서!

가장 작은 직사각형은 4개의 정사각형에 대각선이 표시되고 이것이 최대공약수인 4번 반복되니까

4 * 4 = 16

16개의 정사각형에 대각선이 표시가 되어있다는 것이다

가로 8, 세로 12의 직사각형은 8 * 12 = 96 개의 정사각형을 가지고 있고

이 16개의 정사각형을 빼주면 96 - 16 = 80 우리가 구해야할 멀쩡한 사각형의 개수 80을 구할 수 있다

​

​

그러면 코드를 작성할 때

​

1. 가로(w), 세로(h)의 최대공약수(gcd) 구하기

2. 멀쩡한 사각형 구하기

w * h - (w / gcd + h / gcd - 1) * gcd

➡ w * h - (w + h - gcd)

​

이렇게 공식을 간략화하여 총 정사각형 갯수에서 대각선 표시된 정사각형 갯수를 빼주면 된다

​

끝!

​