JArchive 프로그래밍 일기

문제

멀쩡한 사각형 프로그래머스 level2

리뷰

가로 W, 세로 H가 1억 이하의 자연수로 들어오기 때문에, 변수들을 long long 형으로 처리해줘야 한다.

넓이를 구할 때 얘네를 곱셈을 하니까 int 표현 범위를 넘어설 수 있기 때문이다.

가로, 세로 비율에 따라서 사용불가한 종이의 개수가 일정하다.

최대공약수가 필요하겠다 싶어서 gcd 함수를 만들었다.

// 재귀 형태 GCD
long long gcd(long long a, long long b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

// 반복문 형태 GCD 
int GCD(int a, int b){

    int i = 1;
    for(i = (a<b)? a:b; i > 0; i--){ // 작은 수를 i로 두고 시작 
        if( (a%i == 0 ) && (b%i == 0) ){ // 둘 다 나누어 떨어지는 숫자를 구하면 탈출 ! 
            break;
        }
    }
    return i;
}

너비 W를 gcd 로 나눈 길이와 높이 H를 gcd로 나눈 길이로 된 사각형에서 규칙성이 발견된다.

예를 들어, 가로 8, 세로 12 라면, 최대공약수 gcd가 4이다.

가로 2, 세로 3 사각형 단위로 종이가 총 6칸이다. 여기서 사용불가 종이가 4개씩 발생한다.

사용불가 종이가 가로2 + 세로3 - 1개 씩 발생한다. ( 4 == 2+3-1)

직사각형 종이의 가로 8, 세로12 에서도 최대공약수 만큼 사용불가 종이가 발생한다.

사용불가 16개 == 8 + 12 - 4

총 넓이 (W * H) 에서 16개를 빼면 답이 나온다.

이 때 W, H를 곱한 수가 int 표현범위를 초과할 수 있으니까 전부 long long 으로 처리한다.

코드

using namespace std;

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

long long solution(int w,int h) {
    long long answer = 1;
    long long total =(long long)w * h; // 직사각형의 총 넓이  
    long long gcd_num = gcd((long long)w, (long long)h); // W, H의 GCD 

    answer = total - (w + h - gcd_num);

    return answer;
}

처음 짰던 코드

using namespace std;

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

long long solution(int w,int h) {
    long long answer = 1;
    long long total = (long long)w*h;

    long long gcd_num = gcd((long long)w, (long long)h); // GCD

    long long temp_w = (long long)w / gcd_num; // w를 GCD로 나눈 길이
    long long temp_h = (long long)h / gcd_num; // h를 GCD로 나눈 길이 

    // 사용 불가 종이의 개수  == (temp_w + temp_h -1)
    long long block_cnt = w / temp_w; 
    answer = total - (block_cnt * (temp_w + temp_h -1) );

    return answer;
}