1493 박스 채우기

문제

세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, 4×4×4, 8×8×8, ...)

세준이가 가지고 있는 박스의 종류와 큐브의 종류와 개수가 주어졌을 때, 박스를 채우는데 필요한 큐브의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 세 자연수 length width height가 주어진다.

둘째 줄에 세준이가 가지고 있는 큐브의 종류의 개수 N이 주어진다.

셋째 줄부터 총 N개의 줄에 큐브의 종류 Ai와 개수 Bi가 순서대로 주어진다. 큐브의 종류는 한 변의 길이를 나타낼 때 쓰는 2i에서 i이다.

출력

첫째 줄에 필요한 큐브의 개수의 최솟값을 출력한다. 만약 채울 수 없다면 -1을 출력한다.

 

 

이건 내가 아는 한 역대급으로 어려운 문제였다.

 

1. 동전문제 처럼 풀어서 틀렸다.

2. 남은 공간의 정보를 구하는 힌트를 얻어서 구현해서 시간초과 + 메모리 초과

3. 재귀적인 방법을 찾아서 구현했더니 시간초과

4. 수학적으로 아주 어렵게 푼 공식. (이건 절대 못떠올린다.)

 

C++로 3번이 통과하는것 같은데 2번은 c++로 해도 메모리초과가 났었을 것같다.

 

숫자의 범위가 좀 작았어도 2번으로 풀 수 있었는데, 방법을 강구하다가 너무 많은 시간을 소모해버렸다 ㅠㅠ

 

1. 동전던지기 처럼 풀었다가 틀림

 

import sys
input = sys.stdin.readline

length, width, height = map(int, input().rstrip().split(" "))
n = int(input().rstrip())

cubes = []
for _ in range(n):
    a, b = map(int, input().rstrip().split(" "))
    cubes.append((a, b))
    # for i in range(b):
    #     cubes.append((2**a)**3)

volume = length*width*height

count = 0
while(volume > 0 and len(cubes) > 0):
    line, num = cubes.pop()
    v = (2**line)**3
    for i in range(num):
        if(volume > 0):
            volume -= v
            count += 1


print(count)

 

2. 공간계산해서 풀었더니 메모리+시간초과

import sys
import heapq
input = sys.stdin.readline

length, width, height = map(int, input().rstrip().split(" "))
n = int(input().rstrip())

cubes = []
for _ in range(n):
    a, b = map(int, input().rstrip().split(" "))
    cubes.append([2**a, b])

totalVolume = length*width*height


def getLargestCube():  # 가장 큰 크기의 큐브를 반환한다.
    global cubes

    if(len(cubes) == 0):  # 큐브가 없으면 -1 반환
        return -1

    # 가장 큰 큐브의 개수가 0이상이면 개수를 1개 줄이고 반환한다.
    if(cubes[-1][1] > 0):
        cubes[-1][1] -= 1
        return cubes[-1][0]  # 큐브 크기 반환
    # 개수가 0개이면
    else:
        cubes.pop()  # 0개인거 제거
        return getLargestCube()


def marginSpace(l, w, h, line):  # 공간과 큐브의 한 변이 주어졌을때 나머지 공간 반환
    res = []
    if(h-line > 0):
        res.append((l, w, h-line))
    if(w-line > 0):
        res.append((line, w-line, line))
    if(l-line > 0):
        res.append((l-line, w, line))
    return res


def solve(length, width, height):
    global cubes, totalVolume
    # 크기순 정렬
    cubes = sorted(cubes, key=lambda x: x[0])

    count = 0

    q = []
    heapq.heappush(q, (-1*length*width*height, length, width, height))

    cube_line = 0  # 초기화
    while(len(q) != 0):
        # print(q)
        _, l, w, h = heapq.heappop(q)  # 부피가 큰것부터 꺼낸다.
        # 큐브 준비
        cube_line = getLargestCube()

        if(cube_line == -1):
            break
        # 유효한 범위에 모든 조건이 부합하면
        if(l >= cube_line and w >= cube_line and h >= cube_line):
            count += 1  # 큐브를 넣는다!
            totalVolume -= cube_line**3  # 총 볼륨을 빼준다.
            # 큐브를 넣은 후의 공간을 구한다.
            spaces = marginSpace(l, w, h, cube_line)
            # 구한 공간을 큐에 넣는다

            for i in range(len(spaces)):
                x, y, z = spaces[i]
                if(x > 0 and y > 0 and z > 0):
                    heapq.heappush(q, [-1*x*y*z, x, y, z])
        else:
            cubes.pop()
            heapq.heappush(q, [_, l, w, h])

    return count


ans = solve(length, width, height)

# 빈공간이 남아있다면 -1
if(totalVolume > 0):
    print(-1)
else:
    print(ans)

# print(totalVolume)
# print(ans)

3. 재귀방식으로 풀었더니 시간초과

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

length, width, height = map(int, input().rstrip().split(" "))
n = int(input().rstrip())

cubes = []
for _ in range(n):
    a, b = map(int, input().rstrip().split(" "))
    cubes.append([2**a, b])
cubes = sorted(cubes, key=lambda x: -x[0])
count = 0

PF = True


def recursive_func(l, w, h):
    global PF, cubes, count
    if(PF == False):
        return
    if(l == 0 or w == 0 or h == 0):
        return
    for i in range(len(cubes)):
        if(cubes[i][1] > 0 and l >= cubes[i][0] and w >= cubes[i][0] and h >= cubes[i][0]):
            count += 1
            cubes[i][1] -= 1

            recursive_func(l, w, h-cubes[i][0])
            recursive_func(cubes[i][0], w-cubes[i][0], cubes[i][0])
            recursive_func(l-cubes[i][0], w, cubes[i][0])

            return
    PF = False
    return


recursive_func(length, width, height)

if(PF == False):
    print(-1)
else:
    print(count)

4. 수학공식

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

length, width, height = map(int, input().rstrip().split(" "))
n = int(input().rstrip())

cubes = [0] * 21
for _ in range(n):
    a, b = map(int, input().rstrip().split(" "))
    cubes[a] += b

total = 0
count = 0
for i in range(19, -1, -1):
    total <<= 3
    t = min(cubes[i], (length >> i)*(width >> i)*(height >> i) - total)
    total += t
    count += t

if(total == length*width*height):
    print(count)
else:
    print(-1)

 

 

솔직히 다시는 만나고 싶지 않은 문제이다.