[Python] 1166번: 선물

https://www.acmicpc.net/problem/1166

1166번: 선물

시간제한 2초

메모리제한 128mb

1 ≤ 가로,세로,높이,내용물개수 ≤ 1,000,000,000 (10^9)

 

<문제 풀이전 나의 생각>**************************************************

담는 박스의 가로, 세로, 높이가 주어지고(전체 박스의 사이즈)

 

꼭 N개를 넣어야하는 물건의 개수 N이 주어지는데, 이때 넣는 정육면체의 한변(A)의 크기가 가장 최대로 해야 한다.(그리디하게)

 

그럼 단순하게 1부터 넣어서 10^9까지 대입해보는 경우는 불가능하다.(시간 제한에 걸림)

 

A를 최대&최적으로 하는 수를 찾기위해서는 이분탐색같이 빠르게 찾는 방법을 사용해야 할것 같다.

 

혹은 테스트케이스가 2.0, 3.0처럼 소수점으로 나오는게 수학적 연산(나누기)를 사용하라는 증거인것 같기도 하다.

 

부피의 개념으로 접근해보면 10개의 깍두기를 넣어야 하는 통의 가로, 세로, 높이는 4,2,10이다. 통의 부피는 80이고 10으로 나누면 8이다. 이말은 깍두기의 가로*세로*높이가 뭘 하든 8이하로 나와야 한다는 말이다. 또한 한 변의 길이는 2 이하여야 한다.

 

정사각형 깍두기 조건 1: 담는 통의 가장 작은 한변의 길이 이하여야 한다.

정사각형 깍두기 조건 2: (깍두기(A) 한변의 길이)^3 <=담는통의 부피/깍두기개수

 

이 조건으로 한번 해보자~

 

 

<문제 푸는중 고민>**********************************************************

arr은 정사각형 A의 한변의 길이로 사용가능한 수들의 집합 이다.

당연히 1에 가까워 질수록 많이 넣을수 있고, 끝 인덱스에 가까워 질수록 적게 넣을수 있다는 말이다.

그렇다면 나는 이분탐색을 통해서 now = N, now-1 = N+1이 되게 하는 인덱스 겸 한변의 길이를 의미하는 now를 찾을 예정이다.

 

머리가 아프다. 조건을 다시 고려 해보자

 

XYZ중 가장 작은 변을 천장으로 잡는건 맞다. min(X,Y,Z) =정사각형 한변 라고 하면 넣을수 있는 개수는 최소 1개 이상이다. 이분탐색의 범위를 나는 0~ min(X,Y,Z)로 잡고 탐색을 하였는데

 

이분탐색의 조건이

now-1이 N보다 작고

now가 N보다 크거나 혹은 같게 하는 now 인덱스를 찾으면 된다.

 

이렇게 조건을 잡고 탐색을 진행해야 할것 같다.

 

A^3  <= (X*Y*Z)/N 이 검사 조건식은 필요가 없는듯...

 

import sys


'''
Present, X, Y, Z = map(int, sys.stdin.readline().split())
MAX_A = min(X,Y,Z)



arr = [i for i in range(0,MAX_A+1)]

# (깍두기(A) 한변의 길이)^3 <=담는통의 부피/깍두기개수 조건을 만족하는지 검사하는 함수
def check(A):
    # 이 조건을 만족하면 검토 가능한 해 이다.(최적을 보장하지는 않는다.)
    if A^3<=(X*Y*Z)/Present:
        return True
    else:
        return False


def N_check(A):
    # 몇개가 들어갈수 있는지 판단하는 함수 이게 N과 일치하면서 
    # 그리디 하게 가져가야 하는것이 목표이다.
    return Z*((X*Y)//A*A)
# middle이 check함수를 만족하고, middle+1이 check 함수를 만족하지 않는 middle이 최적값이라고 생각한다.
def binary_search():
    
'''

# 다른분의 풀이 참조 https://sophuu.tistory.com/50
'''
import sys

# 개수, 통가로, 통세로, 통높이
N, L, W, H = map(int, sys.stdin.readline().split())

# 시작, 끝
# 나는 min값을 끝으로 두었는데 이분은 max를 끝값으로 두었다. 이게 확실하기는 하지
# 아무리 커도 max값을 넘지는 않을것이니 
S, E = 0, max(L, W, H)


# 특정 조건을 만족할때 끝내는 이분탐색이 아닌, 10000번 정도면 찾겠지 하는 마인드로 반복문을 돌리는 경우 이다.
# 수렴할때 까지 반복을 진행한다는 말
for _ in range(10000):
    M = (S + E) / 2    #중간값
    # 들어갈수 있는 정사각형의 개수를 의미하는 count
    count = (L // M) * (W // M) * (H // M)
    
    # 한변의 길이를 M으로 둘때 만들어 지는 정사각형의 개수(count)가 
    # 찾고자 하는 N보다 크면 좀더 M의 길이를 늘리는 방향으로 해야 함
    
    # 한변의 길이를 M으로 둘때 만들어 지는 정사각형의 개수(count)가 
    # 찾고자 하는 N보다 작으면 M의 길이를 줄여서 더 많이 담아야 한다.
    
    # 아래의 조건문은 늘렸다, 줄였다 핑앤 퐁을 반복하면서 최적의 값을 찾는 과정 이다.
    # 이래서 소수점이 나왔던 것이였구나...
    if count >= N:
        S = M
    else:
        E = M


# 상한 오차가 10^-9 까지 허용한다는게 무슨 말인지는 잘 모르겠는데
# 일단은 소수점 아래 9자리 숫자까지 허용해보자
print("%.9f" %(E))



'''
# 다시한번 풀어보자

import sys
N,X,Y,Z = map(int, sys.stdin.readline().split())


cnt = 0

start = 0
end = max(X,Y,Z)

while(cnt<100000):
    middle = (start + end) / 2
    now_N = (X//middle)*(Y//middle)*(Z//middle)
    
    # 이렇게 시작을 떙겨오면 now_N이 작아질 확률이 증가함(큼직큼직하게 A를 잡음)
    if now_N>= N:
        start = middle
    else:
        # 이렇게 끝을 땡겨오면 now_N이 커질 확률이 증가함(조금조금 A를 잡음)
        end = middle
    
    cnt+=1
    
print("%.9f" % middle )

 

<문제를 풀고난뒤 후기>*********************************************************

결국 내 자신의 고민으로는 생각하지 못하였다.

 

계속 깨닫는 거지만 이분탐색은 개념 그 자체이지 특정한 구현기술력이나 공식이 아니다.

 

middle 값의 오차를 줄여나가면서 A를 찾는 이분탐색의 공식을 생각하지 못하였다.

 

start와 end의 평균값이 middle로 쓰인다는 발상은 참 기발한것 같다

 

또한 무수히 많은 반복을 통해서 수렴값을 찾는 극한값의 개념이 사용된것 같기도 하다

 

그래도 정수 범위가 10^9까지 인걸 보고 이분탐색을 써야 하는구만~ 한것은 나름 발전이 보인다.

 

깨닫게 된것: 이분탐색을 무조건 배열이나 정수값에 쓰인다고 생각하지 말자, 충분히 큰 숫자범위 내에 최적값을 찾는데 쓸수 있다.(극한값)