[Python] 4349번 Blocks

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

4349번: Blocks

---

 

22/09/24

 

 

브론즈 문제 치고는 살짝 당황하게 만드는 난이도를 가진 문제로, 애를 살짝 먹었다. 개인적으로는 브론즈 2가 아니라 브론즈 1 또는 실버 5 사이에 위치해있어도 괜찮을 법한 난이도를 가진 것 같다.

---

 

문제 접근 방식:

 

 

일단 외국어 문제이니, 문제에서 요구하는 바를 요약하겠다.

 

먼저 테스트케이스의 개수가 주어지고 각 테스트 케이스마다 하나의 숫자가 주어진다.

 

이 숫자는 1*1*1짜리 큐브의 개수인데, 이 큐브의 개수가 주어지면, 이 큐브를 모두 이어붙여서 만들 수 있는 입체도형의 최소 겉넓이를 출력하는 것이 이 문제의 목적이다.

 

처음에는 어떠한 특정 규칙이 있는 줄 알고 굉장히 난감해했었다.

 

어떤 식으로 접근을 해야 이 문제를 풀 수 있는지 생각하기 힘들었기 때문이다.

 

그래서 10분 정도 고민을 해보다가 결국 태그를 공개하여 문제를 해결하였다.

 

주어지는 숫자의 범위가 1000을 넘지 않는다는 점에서 착안하여 단순 브루트 포스로 해결하면 되는 일이었다.

 

하지만, 맨 처음에 그렇게 구현을 했는데, 시간 복잡도가 O(n^3)이고, 크기가 1000이라 1000*1000*1000 = 10억 번이라 시간 초과가 떠버렸다.

 

그래서 그냥 구현하는 것이 아니라 맨 안쪽의 루프를 n번 반복하는 것이 아닌 sqrt(n)번 반복하도록 해주었다.

 

그렇게 해도 가능한 이유는 겉넓이가 최소가 되려면 최대한 큐브들이 서로 맞닿는 쪽으로 큐브를 이어 붙여야 되고, 그러면 큐브를 이어 붙인 모양이 정육면체에 가까워진다고 생각했기 때문이다. (완벽한 정육면체는 아니더라도 최소한 직육면체가 돼야 됨)

 

때문에 부피가 n인 정육면체의 한 변은 n^(1/3)이기 때문에 그거보다 살짝 여유 있게 sqrt(n)번 반복해주도록 구현하였다.

 

이렇게 구현했더니, 맞았습니다를 받았다.(시간 복잡도 O(n^(5/2)))

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 4349번 Blocks
# 수학, 구현, 브루트포스, 기하학
import sys
input = sys.stdin.readline
from math import *

T = int(input())
for _ in range(T):
    possible_set = []
    n = int(input())
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i*j > n:
                break
            for k in range(1, ceil(sqrt(n))+1):
                if i*j*k == n:
                    possible_set.append((i, j, k))
                    break
    min_val = 1e9
    for a, b, c in possible_set:
        if min_val > 2*(a*b + b*c + c*a):
            min_val = 2*(a*b + b*c + c*a)
    print(min_val)

 

---

하지만, 시간을 좀 더 줄일 수는 없을까 고민하다가 맨 안쪽의 루프를 돌지 않고 구현하는 방법을 생각해냈다.

 

나눗셈 연산을 활용하여 k를 구하는 것이다.

 

이러면 시간 복잡도가 O(n^2)으로 줄어든다.

 

확실히 이렇게 구현하였더니 기존 파이썬 코드로 1500ms정도 걸렸던 시간이 200ms정도로 급격히 줄어들었음을 확인할 수 있었다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 4349번 Blocks
# 수학, 구현, 브루트포스, 기하학
import sys
input = sys.stdin.readline
from math import *

T = int(input())
for _ in range(T):
    possible_set = []
    n = int(input())
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i*j > n:
                break
            k = (n // i) // j
            if i*j*k == n:
                possible_set.append((i, j, k))
    min_val = 1e9
    for a, b, c in possible_set:
        if min_val > 2*(a*b + b*c + c*a):
            min_val = 2*(a*b + b*c + c*a)
    print(min_val)