[프로그래머스][코딩연습/level2 수학] 멀쩡한 사각형 파이썬 친절한 설명

문제 설명

가로 길이가 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 을 반환합니다.

 

---

자세한 풀이를 보려면 아래의 노트 필기를 참고하세요~

 

문제를 처음 봤을 때 규칙을 찾는 문제 같다는 생각을 했고 쉽게 풀 수 있을 것 같은 느낌이 왔다.

저 패턴들의 반복이 눈에 걸렸달까....

 

trial & error

def solution(w,h):
	slope = h/2
    count = 0
    for i in range(1,w):
    	count += int(slope * i)
    return count * 2

아래 풀이에도 적혀있는 첫번째 코드이다. 문법적으로 틀린 것은 없으나 이 문제에서 

제한사항

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

이 부분을 주의해야 한다. 항상 문제를 풀 때는 제한사항의 길이를 보고 complexity를 신경 써야한다.

이 함수를 이용한 방법을 사용한다면 W나 H가 1억이라면 반복문으로 그만큼의 횟수를 반복해야 한다.

그래서 시간초과 문제가 발생했다.

 

나의 풀이

def solution(w,h):
	if (w == 1)|(h == 1): return 0
	if (w % h == 0): return w * h - (w + h - h)
	if (h % w == 0): return w * h - (w + h - w)
	
	i = 2
	GCD = 1
	
	w_devided = w
	h_devided = h
	
	while(1):		
		if (i == w_devided)|(i == h_devided):
			break
		
		if (w_devided % i == 0)&(h_devided % i == 0):
			GCD *= i
			w_devided = w_devided/i
			h_devided = h_devided/i
		else: i += 1
	print(GCD)
	return  w * h - (w + h - GCD)

 

최대 공약수를 이용한 풀이이다. 아래의 필기를 보면 알 수 있겠지만 여러 예시를 들어 그리다 보니 알게된 규칙이다. 

풀이를 할 때 잘 모르겠으면 일단 여러 예시를 들어서 규칙을 찾아야 한다. 최대 공약수를 찾는 코드가 생각보다 더럽게 짜져서.. 수정이 필요하다고 본다. 

import math
def solution(w,h): return w*h-(w+h-math.gcd(w,h))

찾아보니 math 모듈에 최대공약수를 구하는 함수가 있더라.. 이를 이용하면 이렇게 간단하게 풀 수 있다.

 

 

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

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