행복한 삶을 찾아서

에라토스테네스고 뭐시기고 필요없다. set() 자료형으로 쉽게 해결.

주어진 수 범위에서 제곱수로 나누어 떨어지는 수의 개수를 뺐다. 주어진 수 범위를 반복문으로 돌면 시간초과.

주어진 예제 입력 외에도 최소/최대 조합인 [1,000,000,000,000, 1,000,001,000,000] 범위로 테스트 해보기. [4, 4] 범위도 0 나오는지 잘 확인해보기

min_num, max_num = map(int, input().split(" "))
# 2 부터 (max의 제곱근 정수부분) 까지 반복문을 돌려서 검사하면?
max_sqrt = int(max_num**0.5)
# min_num보다 크거나 같고 max_num보다 작거나 같은 수 중에서
# 제곱수로 나누어 떨어지는 수를 리스트에 집어넣고 set으로 변환
num_list = []
for a in range(2, max_sqrt+1):
	if a != 1:
		square_a = a*a
		Q_min = min_num//square_a
		Q_max = max_num//square_a
		
		for b in range(max(Q_min,1), Q_max+1):
			if square_a*b >= min_num and square_a*b <= max_num:
				num_list.append(square_a*b)

num_set = set(num_list)
print(max_num-min_num+1-len(num_set))

기초적인 DP 문제이니 점화식을 잘 짜보자.

지금까지 마셔왔던 최대 양과 잔에 든 양을 바탕으로 n번째 잔에서 마실 수 있는 최대 양을 계산하는 것이 관건. 어떤 것을 고르고 어떤 것을 스킵할지에 주목. 반복문 초기에 0, 1, 2 케이스까지 실수없이 계획 세우기.

n = int(input())
wine_list = []

for a in range(n):
	wine_list.append(int(input()))

max_list = [0]*n

'''
n 번째 max_list 값은
1. max_list[n-1] -> n을 skip
2. n + max_list[n-2] -> n-1을 skip
3. n + n-1 + max_list[n-3] -> n-2를 skip
1,2,3 중 max값을 가져간다

itr==2 인 경우는?
1. max_list[itr-1] -> 2를 skip
2. wine_list[2]+wine_list[0] -> 1을 skip
3. wine_list[2]+wine_list[1] -> 0을 skip
'''

for itr in range(n):
	if itr == 0:
		max_list[itr] = wine_list[itr]
	elif itr == 1:
		max_list[itr] = max_list[itr-1] + wine_list[itr]
	elif itr == 2:
		max_list[itr] = max(max_list[itr-1], wine_list[itr]+wine_list[itr-2], wine_list[itr]+wine_list[itr-1])
	else:
		max_list[itr] = max(max_list[itr-1], wine_list[itr] + max_list[itr-2], wine_list[itr]+wine_list[itr-1]+max_list[itr-3])

print(max_list[n-1])