개발 블로그
[Programmers/파이썬] 프로그래머스(Lv.2) 우박수열 정적분 문제풀이 본문
문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/134239
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
사고 흐름
1. 우선 우박수를 구해야겠다
2. 구한 우박수를 이용해서 넓이를 구해야하는데, k와 ranges의 최대 길이가 만개인데 매번 넓이를 구할 수는 없을 것 같다. 미리 넓이를 계산하자 -> DP
문제 핵심과 알고리즘
다이나믹 프로그래밍 (DP)
def solution(k, ranges):
lc = []
area = [0]
res = []
# lc - 우박수 생성
while k>1 :
lc.append(k)
if k%2==0 :
k//=2
else :
k=k*3+1
lc.append(1)
# area: 정적분을 위한 누적 넓이
t = 0
for i in range(len(lc)-1) :
t+=(lc[i]+lc[i+1])/2
area.append(t)
# res: 정적분
n = len(lc)-1
for r in ranges :
a,b = r[0], n+r[1]
if a>b :
res.append(-1.0)
else :
res.append(area[b]-area[a])
return res
우선 우박수를 구한 lc를 사용해서 누적 넓이를 구할 것이다. 누적 넓이를 계산하는 이유는 정적분 계산이 누적 넓이의 뺄셈으로 쉽게 구할 수 있기 때문이다. 그리고 ranges를 돌면서 범위에 맞는 정적분을 한다.
문제 풀면서 헤맸던 부분
없었다
총평
(소요시간: 20분) 딱히 어려운 구현은 없었다. 하지만 문제가 좀 길고 과정이 좀 길어서 차분하게 단계를 정리하고 코드를 짜면 쉬운 문제이다. 그리고 k와 ranges의 크기를 보고 이건 매번 넓이를 계산할 수 없겠다 라고 판단하고 미리 계산하자! 고 방향을 빠르게 잡는게 핵심이다.
'Algorithm' 카테고리의 다른 글
[백준/파이썬] G3_15683 감시 문제풀이/시간 복잡도 줄이기 (2) | 2024.10.03 |
---|---|
[Codetree/파이썬] 돌아가는 팔각 의자 문제풀이 (0) | 2024.09.23 |
[Programmers/파이썬] 프로그래머스(Lv.1) 삼총사 문제풀이 (0) | 2024.08.22 |
[Programmers/파이썬] 프로그래머스(Lv.2) 택배상자 문제풀이 (0) | 2024.08.22 |
[Programmers/파이썬] 프로그래머스(Lv.2) 연속 부분 수열 합의 개수 문제풀이 (0) | 2024.08.22 |