문제요약: 콜라츠 추측을 통해 나온 값들을 그래프에 좌표화 시켜서 적분 하기
해결 방안: 콜라츠 추측을 통해 나온 배열들을 적분 하여 그 적분 값들의 부분 합을 구하기
1.콜라츠 추측의 배열은 단순 구현이므로 조건에 맞게 코드를 짜면된다.
2.콜라츠 추측을 통해 나온 값들은 평면 x,y 좌표에 서 y 값을 담당하고 x 는 조건의 연산을 진행한 횟수인 1씩 늘어 난다고 생각하면 된다.
3. 그래프를 그리고 1칸씩 짤라 보면 항상 사다리꼴 형태의 모양으로 나오고 사다리꼴의 넓이는 (밑변 + 윗변) x 높이 /2 인데
이때 높이는 항상 1로 고정됨을 알 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | def solution(k, ranges): answer = [] #k 부터 시작하므로 배열 s에 k 값을 넣고 선언하기 s=[k] # 콜라츠 추측으로 배열 만들기 while True: if k==1: break elif k%2==0: k//=2 s.append(k) else: k *=3 k +=1 s.append(k) #적분 값을 구하기 위한 배열 sl=[] # 그래프를 그려보면 항상 사다리꼴 임 #사다리꼴 공식을 이용하여 구간마다 적분값 구하기 for i in range(1,len(s)): sl.append((s[i-1]+s[i])/2) #주어진 배열 을 기준으로 계산하기 for i in ranges: #x 는 시작점 y는 끝나는점 x=i[0] #y 는 끝나는점임 #이때 sl 배열을 저장한 배열의 길이 전체 구간의 길이임 #따라서 끝나는점은 sl배열의 길이 - i[1] 으로 y=len(sl)+i[1] #적분에서 x,y 구간이 똑같으면 0이므로 if x==y: answer.append(0.0) #시작점이 끝점보다 크면 -1로 하라 했으므로 elif x>y: answer.append(-1.0) # 모든 구간 부분합에서 끝점과 시작점 구간의 값들을 전부 합쳐주기 else: answer.append(sum(sl[x:y])) return answer | cs |
보통 이런식으로 구현하면 느낌상 백준에서는 얄짤 없이 시간초과 뜨는 것 같았는데
프로그래머스는 관대한것 같은 느낌이다.
