글 읽기 - [2292] 벌집문제 질문있습니다.

k352ex 7년 전 0

작은 수에서는 작동이 잘되는데 문제는 큰 수가 입력되었을때 메모리가 폭발해버리는 현상이 발생합니다. ㅠㅠㅠ

소스를 최적화 해야하는데 감이 오지않아서 질문드립니다. !

리스트에 [1,[2,3,4,5,6] ...] 이런식으로 벌집의 규칙에 따라 계속 삽입을 해서

리스트를 순회하면서 찾고자하는 수가 있다면 출력을 하는 방식으로 작성했습니다.

1,0000 정도 까지는 잘나오는데 그 이상 수가 들어가면 프로그램이 뻗어버립니다.

n = int(input())

bulzip = []
temp = []
count = 1
div_num = 6
for x in range(1,n+1):
	temp.append(x)
	if x == n: # 마지막 종료
		bulzip.append(temp)
	if x == 1: # 1은 그냥 바로 벌집리스트에 삽입
		bulzip.append(temp)
		temp = []
		count = 1
	elif count % div_num == 0: # 6, 12, 18, 24마다 벌집리스트에 삽입
		bulzip.append(temp)
		temp = []
		count = 1
		div_num += 6
	else: 
		count += 1
        
# 몇 번째 벌집인지 찾는 순회탐색
for index, item in enumerate(bulzip):
	if n in item: # n번째 벌집이 몇번째인지 찾는 조건
		print(index+1)

wooljs 7년 전 0

규칙을 찾으신 것 같은데.. index만 가지고 다시 시도해보요.

N이 10억개입니다. 6개마다 삽입되도 대충 1억6천만개가 삽입됩니다.

1억 6천만 * 8byte / 1024 / 1024... 대충 640MB정도 쓰겠네욤.

메모리 제한이 128MB는 훌쩍 넘길것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[2292] 벌집문제 질문있습니다.

k352ex 7년 전 0

wooljs 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말