[BOJ](Python) 4690번 : 완전 세제곱

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

4690번: 완전 세제곱

1. 삼중 포문을 이용한 브루트 포스 풀이

소스 코드는 다음과 같다.

import sys
input = sys.stdin.readline

dic = {}; result = []
test = [i**3 for i in range(101)]
for i in range(2, 100):
    for j in range(i+1, 101):
        for k in range(j+1, 101):
            if i**3 + j**3 + k**3 in test:
                result.append([test.index(i**3+j**3+k**3),i,j,k])
result.sort(key= lambda x: (x[0], x[1]))
for i in range(len(result)):
    print('Cube = %d, Triple = (%d,%d,%d)' %(result[i][0],result[i][1],result[i][2],result[i][3]))

먼저 이 문제에서 제일 먼저 떠오르는 방법은 (a**3 + b**3 + c**3) ** (1/3)을 하는 것인데,

이 경우 Python의 부동수소점 오차로 인하여 세제곱근을 하게되면 상당히 부정확한 값이 나오게 된다.

 

따라서 세제곱근을 하지 않는 방식을 찾아야 했고, 삼중포문을 이용해서 순열처럼 가능한 b,c,d의 경우의 수를 만들었다.

여기에 test 리스트에 세제곱을 했을 때 값을 넣고, 완전세제곱한 값이 test에 있을때 result 리스트에 이 때의 test의 index와 b,c,d를 리스트로 만들어  추가한다.

 

하지만 이 방법은 O(n^4)라는 매우 느린 시간복잡도이기 때문에 이를 더욱 빠르게 하기 위하여 다음과 같이 고안하였다.

 

2. 캐싱 방법을 이용한 O(n^2) 풀이

a**3 = b**3 + c**3 + d**3에서,  a**3 - b**3 = c**3 + d**3으로 식을 바꿨다.

c**3 + d**3 값과 (c,d)를 알고 있을때 c**3+d**3와 a**3 - b**3이 같다면 이 a,b,c,d값을 저장하는 방식을 이용했다.

 

소스 코드는 다음과 같다.

from itertools import combinations
from collections import defaultdict

cache = {c**3 + d**3: (c, d) for c, d in combinations(range(2,101), 2)}
result = defaultdict(list)

for b, a in combinations(range(2, 101), 2):
    key = a**3 - b**3
    if key in cache:
        result[a].append(tuple(sorted([b, *cache[key]])))

for key in result:
    result[key] = sorted(set(result[key]))

result = sorted(result.items())
for key, values in result:
    for value in values:
        print('Cube = {}, Triple = ({},{},{})'.format(key, *value))
 
출처: ngh3053, https://www.acmicpc.net/source/22140446

cache = {c**3 + d**3: (c, d) for c, d in combinations(range(2,101), 2)}

먼저 순열을 통해 딕셔너리에서 c**3+d**3를 key로 (c,d)를 value로 하는 캐싱을 먼저 저장한다.

for b, a in combinations(range(2, 101), 2):
    key = a**3 - b**3

그리고 순열을 이용해 두개의 조합을 가져온 b, a를 가져온다. 이 때, 순열에서 가져온 값은 무조건 b<a를 만족하기 때문에 key = a**3 - b**3으로 설정한다. (완전 세제곱에서 a가 가장 커야하기 때문에)

    if key in cache:
        result[a].append(tuple(sorted([b, *cache[key]])))

key값이 cache안에 있다는 것은 a**3 - b**3 = c**3 + d**3를 만족하는 것 이기 때문에 a를 key로 하고, cache[key]인 c,d와 b값을 tuple로 묶어 value로 만든다. value로 만들 때 (b,c,d)에서 b<c<d 순으로 크기를 조정하기 위하여 sorted를 하고나서 tuple로 넣는다.

 

---

참고: set(result[key])할 때 hashable type이어야 set를 사용할 수 있다. hashable type에는 string, number, tuple만이 가능하므로 list를 사용하지 않고 tuple를 사용하였다.  *밑의 출처에서 내용을 가져왔습니다.

www.acmicpc.net/board/view/43867

글 읽기 - TypeError: unhashable type: 'list' 알고싶어요!

for key in result:
    result[key] = sorted(set(result[key]))

하지만 이대로 끝낼 경우 result[6] = (3,4,5), (3,5,4), (4,3,5)와 같은 같은 key안에 여러개의 중복값이 나타날 수 있다. 이에 value의 값들을 set로 묶어 중복을 제거하였다.

예시)

from collections import defaultdict
result = defaultdict(list)
result['a'].append((1,2,3)); result['a'].append((1,2,3))
result['a'].append((4,5,6)); result['a'].append((4,5,6))
#set 이전
print(result)
>>> defaultdict(<class 'list'>, {'a': [(1, 2, 3), (1, 2, 3), (4, 5, 6), (4, 5, 6)]})

#set 이후
result['a'] = sorted(set(result['a']))
print(result)
>>> defaultdict(<class 'list'>, {'a': [(1, 2, 3), (4, 5, 6)]})

c = ((1,2,3),(1,2,3),(4,5,6))
print(set(c))
>>> {(4, 5, 6), (1, 2, 3)}

---

result = sorted(result.items())

마지막으로 딕셔너리를 그대로 호출하게 되면 a**3 = b**3 + c**3 + d**3에서 a를 기준으로 정렬이 되도록 해준다.

참고: [Python] 딕셔너리 정렬하기, 1. Key를 이용한 정렬, kkamikoon.tistory.com/138

[Python] 딕셔너리 정렬하기

결론:

1번 풀이는 약 392ms

2번 풀이는 약 88ms로 4배 가까이 빠름을 알 수 있다.

1번 풀이 시간

2번 풀이 시간