백준 1660번 캡틴 이다솜
문제풀이
사용한 알고리즘 : DP
(1) 코드 6~8
'triangle[k] = 사이즈 k의 사면체 만들 때 필요한 대포알 수'라고 설정하였습니다.
N이 최대 3*10^5 으로 주어지므로, 배열 크기는 넉넉히 200 정도로 했습니다.
(2) 코드 31~34
과정(1)에서 만들어 놓은 사면체를 만들 때 필요한 대포알 개수를 구해줍니다.
i번째에서 추가되는 대포알 수는 1+2+...+i = i*(i+1)/2 인 것을 생각해줍니다.
(3) 코드 8~10
'dp[x] : x개의 대포알로 만드는 최소 사면체 수' 라고 설정하였습니다.
(4) 코드 12~27
임의의 수 x가 주어졌을 때, x개의 대포알로 만드는 최소 사면체 수를 구하는 함수입니다.
주어진 x크기로 만들 수 있는 k사이즈의 사면체를 각각 만들어 보면서,
구하고자 하는 x개의 대포알로 만드는 최소 사면체 수를 구하고, 이를 dp로 저장합니다.
댓글
댓글 쓰기
긴 글 읽어주셔서 감사합니다.
궁금한게 있으시다면 댓글 달아주세요!