제로베이스 20220307

코딩테스트 연습

1. 해밍 수열

• 세 소수 p1, p2, p3을 이용해서 해밍 수열 H(p1, p2, p3), i = 1… 을 정의할 수 있다.

• 해밍 수열 H(p1, p2, p3)은 소인수가 p1, p2, p3로만 이루어진 자연수의 오름 차순 목록이다.

• 예를 들어, H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, … 이고, 5번째 수는 6이다.

입력

• 첫째 줄에 p1, p2, p3, i가 주어진다. 네 정수는 10^18보다 작다.

출력

• H(p1, p2, p3)의 i번째 수를 출력한다. 출력하는 수는 10^18보다 작다.

풀이

# your code goes here
 
import sys
 
# 첫째 줄에 p1, p2, p3, i가 주어진다
# 해밍 수열 H(p1, p2, p3)은 소인수가 p1, p2, p3로만 이루어진 자연수의 오름 차순 목록이다.
# H(p1, p2, p3)의 i번째 수를 출력한다. 출력하는 수는 10^18보다 작다.
 
p1, p2, p3, i = list(map(int,sys.stdin.readline().split()))

# p1 ** num1 * p2 ** num2 * p3 ** num3 = 해밍 수열을 이루는 자연수.
# p1, p2, p3을 n번(0 <= n < i) 선택하는 경우의 수와 같다.

h = []

# 계속 최대치에 대한 조건을 달아주어 시간과 메모리를 절약한다.
for num1 in range(0,i+1):
	if p1 ** num1 > 10 ** 18:
		break
	else:
		for num2 in range(0,i+1):
			if p1 ** num1 * p2 ** num2 > 10 ** 18:
				break
			else:
				for num3 in range(0,i+1):
					if p1 ** num1 * p2 ** num2 * p3 ** num3 > 10 ** 18:
						break
					else:
						h.append(p1 ** num1 * p2 ** num2 * p3 ** num3)

 
h.sort()
print(h[i])

풀이 여담

• p1,p2,p3의 조합이라는 아이디어 도출까지는 좋았으나, 그걸 반복문으로 구현하려해서 메모리 부족, 시간 부족등의 오류로 고생했던 문제.

• 결국 지저분하지만 모든 반복문에 최대치에 대한 조건을 달아주는것으로 시간 내에 통과할수 있었다.

• 분명 정렬 문제를 선택했는데 까고보니 경우의 수 문제가 더 많은것 같은 기분이 든다.

채점 결과

• 정답

• 다른 상위권 제출자들 역시 while문을 활용한 반복문이라는 차이를 제외하면 비슷했기에 따로 더 나은 해법을 정리하지는 않는다.