# Summer/Winter Coding(2019) - 멀쩡한 사각형

- Author: @mildsalmon
- Published: 2021-10-12
- Updated: 2021-10-16
- Source: http://blex.me/@mildsalmon/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-summerwinter-coding2019-%EB%A9%80%EC%A9%A1%ED%95%9C-%EC%82%AC%EA%B0%81%ED%98%95
- Tags: 파이썬, 알고리즘, 프로그래머스, 코딩테스트, 문제, summerwintercodin

---

# 1. 멀쩡한 사각형

- 난이도
	- Level 2
- 출처
	- [코딩테스트 연습 - 멀쩡한 사각형 | 프로그래머스 (programmers.co.kr)](https://programmers.co.kr/learn/courses/30/lessons/62048)

### A. 📜 문제

위 프로그래머스 사이트에 접속하여 문제를 확인해주세요.
	
### B. 💡 내 답안

##### a. 😅 1차 시도 (실패)

```python

def solution(w,h):
    total_count = w * h
    
    if w == 1 or h == 1:
        return 0
    
    if w % h == 0:
        return total_count - h * (w // h)
    
    if h % w == 0:
        return total_count - w * (h // w)

```

```

채점 결과

정확성: 50.0

합계: 50.0 / 100.0

```

##### b. 😊 2차 시도 (성공)

```python

import math

def solution(w, h):
    gcd = math.gcd(w, h)
    
    if gcd == 1:
        answer = w + h - 1
    elif gcd > 1:
        answer = gcd * ((w // gcd) + (h // gcd) - 1)
    
    return w * h - answer

```

##### c. 🙄 회고

> 내 풀이

- 내 손으로 그리는 그림은 완전한 정사각형이 아니라서 ppt를 통해 그려보면서 풀었다.
- w와 h를 1부터 늘려가는 방법으로 풀었다.
	- w 혹은 h가 1이면 모든 칸이 대각선 방향으로 잘려서 사용할 수 있는 사각형이 없다.
		![](https://static.blex.me/images/content/2021/10/13/2021_10_13_8_it9sjko7H6V6fEgwJ3VU.jpg)
	- h를 2에 고정하고 w만 늘려보자.
		![](https://static.blex.me/images/content/2021/10/13/2021_10_13_8_jV6FsrhnxcZnpXDaf2QW.jpg)
		- w가 h(2)의 배수가 되는 경우에만 사각형이 딱 나눠 떨어진다.
		- 색칠된 칸 중 겹치는 칸이 없으므로 한 행에 색칠되는 칸을 구하고 행을 곱하면 값이 나온다.
		- 이것을 공식으로 풀어보면, (w // h \* h) 이다.
	- w가 h의 배수가 되지 않는 경우에는 값의 패턴을 발견하기 힘들었다.
		![](https://static.blex.me/images/content/2021/10/13/2021_10_13_8_SLKuG17KeWYCKR7QkDd8.jpg)

> 반성

- 애초에 배수로 접근하면 풀리지 않는 문제였다.
- 문제를 보고 수학이라는 느낌은 왔지만, 한번에 최대공약수가 떠오르지는 않았다.

> 결론

- 뭐... 많이 풀어봐야겠다. 다른 방법이 없다.

### C. 🧐 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

![](https://static.blex.me/images/content/2021/10/13/2021_10_13_8_zAXEBEUfvXI3oV1ro7GL.jpg)

![](https://static.blex.me/images/content/2021/10/13/2021_10_13_8_1GvRuHfyZwqlyp8y9TxU.jpg)

# 참고문헌

Summer/Winter Coding(2019). [코딩테스트 연습 - 멀쩡한 사각형 | 프로그래머스 (programmers.co.kr)](https://programmers.co.kr/learn/courses/30/lessons/62048). Programmers. (accessed Oct 12, 2021)