[PGM_62048] 멀쩡한 삼각형 (java)

문제링크

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

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

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 최대공약수

최대공약수를 활용하여 문제를 해결할 수 있다. 가로와 세로의 최대공약수를 구해주게 되면 가로와 세로의 비율을 알 수 있게된다.

즉, 대각선으로 그었을 때, 가로와 세로의 비율 만큼의 값이 동일한 패턴으로 잘려지게 될 것이다.

예를들어 예시의 내용을 참고하면, 세로의 길이 12 가로의 길이 8로 비율은 3:2가 된다. 그러면 세로 3칸, 가로 2칸의 크기만큼의 패턴이 반복되며 잘려지는 것을 알 수 있다. 그 이유는 3:2의 비율의 칸마다 꼭지점이 찍히기 때문이다. 따라서 최대공약수를 구해주고 비율을 체크하여 잘라서 생각해주었다.

 

최대공약수를 구하는 방법은 유클리드 호제법을 재귀를 이용하여 구현하였다.

-> 2021.10.10 - [CordingTest/Algolithm] - 최대, 최소공배수 그리고 소수를 참고하기 바란다.

 

이제 반복되는 패턴속에서 잘려나가는 종이의 개수를 고려해야한다. 우선 세로에서 봤을 때 무조건 1개씩은 잘려나가게 된다. 대각선으로 그어주기 때문이다. 따라서 하나의 패턴에서 항상 $h/gcd$개 만큼은 remove해주어야 한다. (세로로만 보면)

 

그렇다면 문제는 대각선으로 그을 때 가로로 겹치는 경우를 생각해 주어야한다. 가로로 한줄을 고려하였을 때 그어지는 경우는 1칸 ~ $w/gcd$칸이라고 할 수 있다. 따라서, 가로줄의 겹치는 칸을 지워주기 위해서는 $w/gcd$를 지워주어야한다. (가로로만 보면)

 

이때 시작 점이 항상 같기 때문에 1을 빼주어야한다. 최종적으로 지워주어야 하는 값은 $((h/gcd) + (w/gcd) -1) $이 된다.

 

위 패턴이 총 gcd만큼 실행되기 때문에 최종적으로 전체 칸에서 $((h/gcd) + (w/gcd) -1) * gcd$ 만큼 제거해주면 된다.

구현코드

package pgm_62048;

class Solution {
    public long solution(int w, int h) {
        long answer = 1;
        int gcd = gcd(w, h);
        long remove = ((h / gcd) + (w / gcd) -1) * gcd;
        answer = ((long)w * (long)h) - remove;
        return answer;
    }

    public int gcd(int a, int b) {
        if (a % b == 0)
            return b;
        else
            return gcd(b, a % b);
    }
}

 

시간복잡도

gcd를 구해주는 경우가 가장 크며 w,h중의 큰 값을 n이라고 하면 O(n)이라고 할 수 있다.

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)