Summer/Winter Coding`19 - # 1. 멀쩡한 사각형

코딩테스트 연습 - 멀쩡한 사각형 | 프로그래머스 스쿨 (programmers.co.kr)

1. 멀쩡한 사각형

문제 설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한사항

• W, H : 1억 이하의 자연수

입출력 예

WHresult

8

12

80

입출력 예 설명

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

---

[문제 해설]

 

1. w와 h의 기울기 관점으로 문제를 보아야한다.

2. 직선이 좌표의 점을 만나기 전까지 사각형을 파괴한다.

3. 그렇다면 좌표는 언제 만날까? 해당 좌표의 가로 또는 세로의 배수가 w 와 h일때 좌표를 지나간다.

4. 점이 만나기전까지 사각형이 파괴된다 => 점을 만나려면 각 좌표의 배수가 w 와 h 가 되는지 알아야 한다

4-1. 즉 w와h의 최소공약수가 될때마다 사각형이 일정 수만큼 파괴된다 => 최대 공약수만큼 사각형이 파괴된다.

4-2. 그럼 최대공약수 크기가 될때마다 얼마나 파괴되는지 알아야한다!

5. 좌표적으로 생각을 해야합니다.  예제를 예로 들어봅시다. w = 8 , h = 12 이고 gcd = 4입니다.

5-1. y = (3 * 4/2 * 4) * (x) 직선은 => y = (2 / 3) * x로 표현할 수 있겠죠...! 자 좌펴적으로 생각해봐요

5-3. (2 / 3) * x 가 좌표를 지나는 점은 2 / 3 * x 배수 만큼 될때 만난다는 뜻입니다. 

5-4. 즉, 점을 지나기전에 사각형을 파괴되는... 즉 좌표평면에서 직선에의해 사각형을 지나가는 직선은 2 / 3 x 로 보면

2 * 3 = 6 개의 사각형 중에 2 / 3 * 6 = 4개의 사각형이 파괴된다는 뜻이 되는 것 입니다.

5-5. 이 파괴되는 사각형의 수가 gcd만큼 나오므로 4 * gcd가 파괴되는 사각형의 전부가 되고

6. 이걸 w * h에서 만큼 빼주면 됩니다.

 

---

[코드]

 

# 재귀 호출 사용
def gcd(a, b):
    if a % b == 0 :
        return b
    elif b == 0 :
        return a
    else:
        return gcd(b, a % b)

def solution(w, h):
    answer = 1 
    if w > h:
        gcdVal = gcd(w, h)
        a = w // gcdVal
        b = h // gcdVal
        answer = w * h - (gcd(w, h) * (a + b - 1))
    else:
        gcdVal = gcd(h, w)
        a = w // gcdVal
        b = h // gcdVal
        answer = w * h - (gcd(w, h) * (a + b - 1))
    return answer

 

---

후기

 

좌표적으로 생각하는게 어렵고

문제가 수학문제 같다.

못풀어도 넘어가도 될듯하다.