프로그래머스 윈터코딩(2019) 문제1: 멀쩡한 사각형

문제 출처: 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억 이하의 자연수

입출력 예

W                                 H                                result

8

12

80

 

접근 방법

실제 윈터코딩 인턴을 뽑는 과정에 지원해서 실제로 참가했었지만... 나를 당황시켰던!? 문제이다.(2번 문제도 잘 못 풀고 SQL 문제도 못 치고... 난 언제쯤 잘 풀려나 ㅠㅠ) 한참 여러가지 가로, 세로 길이의 직사각형 케이스를 그려보면서 패턴을 찾으려고 했다. 2~3개 정도 케이스를 보았을 때, 기울기 값을 (h/w) 올림 하여 기울기의 w로 곱한 값이 사용할 수 없는 정사각형의 개수라고 파악하였다. 하지만 테스트 결과 38점 정도로 낮은 정답률을 보였다. 이내 다른 케이스에서 (가로 세로 편차가 많이 난 경우) 내가 가정한 패턴과는 달리 사용할 수 없는 정사각형의 개수가 불규칙적으로 증가하였다. 내가 세운 규칙성이 잘못됐음을 인지하고 다시 기울기를 어떻게 활용할지에 대한 생각을 내리다가, 반복문을 통해서 한 줄씩 사용할 수 없는 정사각형의 개수는 더해가는 방식을 적용했다. 코드는 아래와 같다.

public class Solution {

    public long solution(int w, int h) {
        long answer = 1;
        long W = (long)w;
        long H = (long)h;

        long total = W * H; //총 정사각형 갯수

        if (H > W) { //무조건 W가 h보다 큰 값으로 만들겠다 !
            long temp = H;
            H = W;
            W = temp;
        }

        if (H == W) { // 정사각형의 경우
            return total - W;
        }

        double slope = (double) H / W; //실제 기울기 (double형으로 제대로 표현 되야한다!) (1보다 작거나 같은 수)

        long cutsquare = 0;

        for (long i = 1; i <= W; i++) {

            double befval = slope * (i - 1);
            double curval = slope * i;

            if (Math.floor(befval) == Math.floor(curval) ||
                    Math.ceil(befval) == Math.ceil(curval))
                cutsquare += 1;
            else
                cutsquare += 2;

        }

        answer = total - cutsquare;

        return answer;
    }
 }

 실제로 이 방식을 적용하였을 경우에, 점수가 대폭 상승했으나 테스트 케이스 12~ 16번이 계속 틀렸다고 나왔다.
한참을 이리저리 코드를 변경해보았는데, 도무지 답이 안나와서 '질문하기'에 가서 약간의 팁을 받았다.
감사하게도 어떤 분이 자료형에 대한 지적을 하는 답글을 봤다. 문제 조건에서 w와 h의 제한조건이  '1억이하의 자연수'라는 점을 간과 했다는 것이다. 곧바로 w와 h를 바로 long 타입의 W와 H(변수는 왠만하면 소문자로 쓰고 싶지만 너무 길어지는 것을 방지하고 싶었다)로 형변환을 하여 문제에 적용했더니 곧바로 문제를 통과할 수 있었다. 

다른 사람들의 풀이가 궁금해서 찾아보니 대다수가 gcd(int w, int h) 함수를 많이 썼었다. 여러 답변에서 똑같이 등장하기 때문에 어떤 공통된 의미가 있을 것이라 생각하고 찾아보니 

GCD (Greatest Common divisor) - 최대공약수 

위와 같았다. 즉 다른사람들은 대부분이 최대공약수를 이용하여 문제를 해결하였다는 것이다.
다른 사람들의 풀이는 answer = 총 정사각형 개수 - (가로길이 + 세로 길이 - 최대공약수)였고 그 대략적으로 계산하였을 때, 같은 결과가 나타났다. ( 그 이유를.... 잘 모르겠다 다시 한번 생각해보기로 했다)

gcd함수를 직접 구현하여 사용하거나 혹은 BigInteger 클래스에 gcd() 메소드를 바로 사용하는 방법도 있다.
알고리즘 게시판에 별도로 올리는 것으로 한다.