문제 링크
문제 요약
주어진 에너지 e에 대해, 다음 조건을 만족하는 음이 아닌 정수 x, y, z를 찾아야 합니다:
x + y^2 + z^3 = e- 위 조건을 만족하는
x, y, z중x + y + z의 값을 최소로 만들어야 합니다.
이렇게 찾은 x + y + z의 최소값을 출력해야 합니다.
입력 e는 1부터 1,000,000까지의 양의 정수이며, e = 0이 입력되면 프로그램이 종료되어야 합니다.
풀이
주어진 e에 대해 x + y^2 + z^3 = e를 만족하면서 x + y + z를 최소화하는 x, y, z 쌍을 찾아야 합니다. 여기서 x, y, z는 모두 음이 아닌 정수여야 합니다.
x, y, z가 음이 아닌 정수라는 조건과 e의 최대값이 1,000,000이라는 점을 활용하여 탐색 범위를 좁힐 수 있습니다.
z^3 <= e이므로,z의 최대값은e^(1/3)입니다.e = 1,000,000일 때,z의 최대값은100입니다.y^2 <= e이므로,y의 최대값은e^(1/2)입니다.e = 1,000,000일 때,y의 최대값은1,000입니다.
x = e - y^2 - z^3 이라는 관계가 성립하므로, y와 z의 값을 정하면 x는 자동으로 결정됩니다.
우리가 해야 할 일은 x가 음이 아닌 정수가 되는 유효한 (y, z) 쌍을 모두 탐색하고, 각 쌍에 대해 x + y + z 값을 계산하여 그 중 최소값을 찾으면 해결할 수 있습니다.
정답 코드
- pypy로 제출해야 함.
def find_square_count(limit, k):
count = 0
while count ** k <= limit:
count += 1
return count - 1
def solve(e):
mx_z = find_square_count(e, 3)
mx_y = find_square_count(e, 2)
ans = float('inf')
for z in range(mx_z + 1):
for y in range(mx_y + 1):
x = e - (y * y + z * z * z)
if x < 0: continue
ans = min(ans, x + y + z)
print(ans)
if __name__ == "__main__":
while 1:
e = int(input())
if e == 0:
break
solve(e)