멀쩡한 사각형

이번 문제는 컴퓨터 그래픽스의 선분 Plot과 유사한 문제입니다.

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

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

 

문제를 예시를 보면, 아래와 같습니다.

문제의 예제(Ex. W = 8, H = 12)

모눈종이 위에 직선을 긋고, 해당 직선이 지나가는 경우에는 해당 부분을 제거한 다음

 

남아있는 회색의 정사각형 갯수를 반환해야 합니다.

 

이때 컴퓨터그래픽스 내용을 포스팅하면서, 선분을 Plot하는 DDA방법이 있다고 말씀드렸었습니다.

 

DDA방법을 이용한 문제풀이 방법을 살펴보면

 

1. W와 H를 비교하여, H를 크게, W를 작게 SWAP해준다.

2. 위 W,H를 기반으로 선분의 방정식을 산출한다.

3. 0~W까지 1씩 증가시키며 Start지점과 Start+1 지점의 Y값을 구한다.

4. Start의 Y값은 내림, Start+1의 Y값은 올림 한 후 두 값의 Delta값을 구한다

5. Start+1이 W에 도달할때까지 1~4를 반복

 

하지만, 잘 생각해보면 특정 값을 기준으로, 반복적인 패턴이 나오는 것을 알 수 있습니다.

(위 이미지에서는 W가 1~2까지 나온 패턴이 마지막까지 반복됩니다)

==> 이때 W,H의 최대공약수를 구해주면 최소의 반복패턴을 구할 수 있습니다.

 

따라서 알고리즘이 약간 수정됩니다.

3. 0~W까지 1씩 증가시키며 Start지점과 Start+1 지점의 Y값을 구한다.

 ==> 0~min_Loop(최소의 반복패턴)까지 로 변경됩니다. 

 

이렇게되면 반복되는 부분에서의 부동소수점 연산을 피할 수 있습니다.

 

이제 min_loop+1~W사이의 남은 부분만 추가적으로 계산하면 원하는 답을 얻을수가 있습니다.

(0~min_loop부분의 값을 List로 저장한 다음 참조하는 방식으로 해봤는데, 이게 훨신 느립니다)

 

※주의.

해당 문제는 이상하게 i*h/w로 할 경우 부동소수점 연산에서 오차가 발생한다고하니, 참고하세용

programmers.co.kr/questions/14210

프로그래머스

 

Python으로 풀어본 해답입니다 :)

import math

def solution(w,h):
	#반복횟수를 줄이기 위해서 W가 H보다 클 경우 Swap을 해 줍니다.
    if w>h:
        temp = w
        w = h
        h = temp    
    
    answer = 0    
    #이때 최소반복패턴을 찾기 위해서 W,H의 최대공약수를 찾고
    #최대공약수를 이용해서 W의 최소반복횟수를 찾습니다.
    cal_ran = int(w/math.gcd(w,h))    
    #최소반복패턴에서 필요한 정사각형의 개수를 계산합니다.
    for i in range(cal_ran):
    	#Start지점의 내림값과 End지점의 올림값의 Delta만큼 정사각형이 필요합니다.
        #이때, W,H를 변환 후 원점을 지나게 해도 해는 동일합니다.
        #때문에 i * (w/h) = x * slope 형태로 식을 써줘도 무관합니다.
        #해당 문제에서 i * (w/h)로 사용할 경우 부동소수점 오차가 발생합니다.
        temp_start = math.floor(float(i/w*h))
        temp_end = math.ceil(float(((i+1)/w*h)))
        answer = answer + int(temp_end-temp_start)        
    
    #최소반복패턴을 이용해서 반복되는 구간에서 필요한 정사각형을 구합니다.
    n = 0
    while w-n*(cal_ran)>0:
        n +=1
    answer = answer * n

	#이제 반복패턴 이후에 완전한 패턴이 되지 못하는 부분을 계산합니다.
    #계산과정을 위 일반 알고리즘과 동일하나, 종료지점이 W가 아닌 Remain입니다.
    remain = w-n*(cal_ran)
    for i in range(remain):
        temp_start = math.floor(float(i/w*h))
        temp_end = math.ceil(float(((i+1)/w*h)))
        answer = answer + int(temp_end-temp_start)
    return w*h - answer