[programmers] Lv.2 멀쩡한 사각형(c++) - 1st

그려서 겨우 풀었지만, 너무 와닿지 않는다.

*문제를 눈으로 풀지 말것*

 

using namespace std;

int gcd(int x, int y){
    if(y == 0) return x;
    else if(x == 0) return y;
    
    return gcd(x%y, y%x);
}

long long solution(int w,int h) {
    if(w == h) return (long long) w*(h-1);
    int gcd_val = gcd(w, h);
    
    int deleted = h/gcd_val + w/gcd_val - 1;
    long long answer = (long long)w*h - deleted*gcd_val;
    return answer;
}

---

문제

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

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

728x90

---

[접근 1]

gcd 구하기: 유클리드 algorithm (이산수학 시간에 배웠던것같다)

어차피 나머지이기 때문에, 큰 값으로 작은 값을 나누면 작은값은 그대로 남는다.

따라서 작은값 큰 값 구별 없이 그냥 나머지 구해주면 된다.

(그런데 다른 사람들은 이렇게 하지 않았음)

int gcd(int x, int y){
    if(y == 0) return x;
    else if(x == 0) return y;
    
    return gcd(x%y, y%x);
}

 

x와 y 위치를 바꿔서 넣어주면 x위치에 있는 값만 0인지 확인해주면되고,

y만 x로 나눈 나머지를 구해주면 된다.

int gcd(int x, int y){
    if(x == 0) return y;
    return gcd(y%x, x);
}

OR

int gcd(int x, int y){
	return x? gcd(y%x, x): y;
}

---

[접근 2]

만약 w와 h가 같으면 그냥 height에서 1뺀 넓이를 구해서 return 해주면 된다.

if(w == h) return (long long) w*(h-1);

---

[접근 3]

그게 아니면 좀 구해야할 것이 있는데, w와 h의 gcd를 구해준다.

작은 직사각형 내에서 지워지는 사각형의 개수는 왼쪽에서 봤을때, h/gcd_val만큼 지워지고, 위에서 봤을때, w/gcd_val만큼 지워지는데, 왼쪽 위 모서리가 두번 카운트 되므로 1만큼 빼준 값이 지워진다.

따라서 답은 전체 넓이에서 작은 직사각형 내에서 지워지는 사각형의 수 곱하기 gcd 값이 된다.

int gcd_val = gcd(w, h);

int deleted = h/gcd_val + w/gcd_val - 1;
long long answer = (long long)w*h - deleted*gcd_val;
return answer;