탐색 범위를 줄여야하는 브루트포스 연습2 - 컴퓨터로 종이접기?

12979번: 종이 접기

 

종이의 크기 W,H인 종이가 주어질때 종이를 적절히 접어서 넓이가 A가 되도록 만들고 싶다.

 

종이를 접더라도 직사각형이 되도록 접어야하고 접고 나서도 W,H는 항상 정수가 되어야한다.

 

여기서 W,H가 10^9까지인데 A가 10^5까지라는 점에 주목하자.

 

W,H로 뭔가 해보는건 어려울것 같지만 적어도 A는 1~10^5까지 다 돌아볼만하다.

 

X*Y = A가 될려면 당연히 X,Y는 A이하여야한다.

 

그래서 A를 기준으로 1~A까지 돌아서 그 값을 X라고 둔다면, Y는?

 

A가 X로 나누어 떨어질때, Y = A//X가 된다.

 

이러한 X,Y를 찾았다면 주어진 W,H에서 찾은 X,Y로 몇번만에 이동할 수 있는지 체크하면 된다.

 

 

W에서 X로 갈려면 가장 빠르게 갈려면 몇번만에 갈수 있을까?

 

길이가 W인 종이를 접을때, 생각을 해보면...

 

가장 많이 줄일려면 W가 짝수이면 W//2까지이고 W가 홀수이면 W//2+1이다.

 

 

 

 

목표로 만들고 싶은 X에 대하여, W//2(혹은 W//2+1)가 X보다 작거나 같다면?

 

접어서 X로 만들 수 있다는 뜻

 

하지만 W//2(혹은 W//2+1)이 X보다 크다면? 아직은 X로 못만드니 더 접어야한다는 뜻

 

def f(w,x):
    
    count = 0

    while w > x:
        
        if w % 2 == 0:
            
            m = w//2
        
        else:
            
            m = w//2+1
        
        count += 1

        if m <= x:

            return count  
        
        w = m
    
    return count

 

 

W에서 X로 가기 위해 몇번 접어야하는지 함수를 구했다면... 이제

 

모든 x = 1,2,3,...,a에 대하여 전부 시도해보고 가장 작은 count를 찾는다

 

여기서 주의해야할 점은?

 

x = 1,2,3,..,a까지 조사하는건 좋지만 당연히 x는 w보다 작거나 같아야한다.

 

마찬가지로 w보다 작거나 같은 x에 대하여 a가 x로 나누어 떨어질때 y = a//x이겠지만

 

이 y도 당연히 h보다 작거나 같아야한다.

 

이렇게 목표로 하는 x,y를 찾았다면 f(w,x)와 f(h,y)의 합이 접어야하는 횟수이고, 가능한 모든 x에 대해 최소 횟수를 찾는다

 

최솟값이 갱신되지 않으면 접어서 넓이가 a가 될 수 없다는 뜻

 

w,h,a = map(int,input().split())

INF = 100000000000000000000000000000
answer = INF

for x in range(1,min(w,a)+1):
    
    if a % x == 0:
        
        y = a//x

        if y <= h:

            count = f(w,x) + f(h,y)

            if answer > count:
                
                answer = count

if answer == INF:
    
    print(-1)

else:
    
    print(answer)