[프로그래머스 Level 2 멀쩡한 사각형] 문제 풀이(Java) - 서머 코딩 2019

해당 문제는 알고리즘보다는 아이디어를 떠올리는 것이 중요하다.

요새 브루트 포스, Dp, 이분 탐색 관련 문제만 풀다보니까 단순 아이디어 떠올리는데 꽤나 오래걸렸다,,,

 

 

문제보기

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

입출력 예 설명

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

나의 풀이

 

접근방식을 떠올리는데 오래걸렸습니다,,,,, 규칙을 찾기 위해 홀수x홀수 사각형, 홀수x짝수 사각형, 짝수x짝수 사각형 모두 그리면서 떠올린 결과 패턴이 반복되는 형태는 최대 공약수였습니다.

(앞으로 직사각형, 정사각형에서 막대기 놓기, 대각선 긋기같은 문제는 최대공약수를 떠올리는 걸로,,,)

 

 

상세 풀이 과정은 아래에 설명하겠습니다.

패턴이 반복되는 형태를 아이패드로 나타내본 것!

 

다음과 같이 그림을 그려보면 대각선이 그려지는 사각형 모양의 패턴이 발견됩니다! 그리고 그 패턴 사각형은 최대공약수에 의해 계산되는 것!입니다.

즉, 6x10 사각형에서 최대공약수는 2니까 각 w, h를 2로 나눈 3x5의 패턴 사각형이 2개 존재한다는 뜻이죠!

 

그렇담 3x5 사각형에서 대각선에 의해 지워지는 사각형이 몇 개냐!가 중요한데요

N*M 사각형에서는 (N + M - 1)개의 사각형이 지워진답니다

 

3X5 사각형에서는 3+5-1개가 없어지는 것이죠

 

이렇게 해서 구현한 다음 코드를 실행해 보았더니!

 

아,,,, 테스트 케이스 3개가 오류가 나더군요!

w, h가 1억 이하의 자연수므로 결과값이 매우 크기 때문에 long으로 answer를 선언해주고 함수 parameter로 받아온 w,h도 long으로 바꾸고 계산을 해야 통과가 됩니다

기억하자! '틀렸습니다'뜨면 long으로 타입 변환,,,,

 

 

코드

 

class Solution {
    static long gcd(long w, long h){
    if(h == 0)
        return w;
    return gcd(h, w%h);
    }
	public long solution(int w,int h) {
		long answer = 1;
        
        long w1 = (long)w;
        long h1 = (long)h;
        long num = gcd(w1, h1);    //최대 공약수 구하기
        
        // (w/최대공약수) * (h/최대공약수)의 패턴이 (최대 공약수)개 존재
        answer = w1*h1 - ((w1/num + h1/num - 1) * num);
		return answer;
	}
}

 

문제를 통한 교훈

 

1. 정사각형, 직사각형 문제는 최대공약수에 해답이 있다

2. large testcase에서 오류가 나는 경우에는 타입 변환!