algospot 회전초밥(문제 ID: SUSHI)

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/SUSHI

algospot.com :: SUSHI

입력으로 예산과 초밥의 종류 수, 각 초밥에 가격과 선호도가 주어졌을때, 예산에 맞게 초밥을 갯수 상관없이 구매하여 구할 수 있는 최대 선호도를 출력하는 문제이다.

초밥을 종류별로 탐색하면서 (예산 - 탐색중인 초밥의 가격)을 예산으로 하는 DP를 이용하여 문제를 풀수있다.

이때 주의할 점은 예산의 범위가([1,10^9]) 너무 커서 메모이제이션을 위한 배열을 예산크기만큼 선언하기 힘들다는것이다.

DP에서 (예산 - 탐색중인 초밥의 가격)을 이용한다 했을때 (탐색중인 초밥의 가격+1)만큼의 배열만 있으면 슬라이딩윈도를 사용하여 문제를 풀기 충분할거 같다.

따라서 기존에 사용하던 재귀적인 DP가아니라 슬라이딩윈도를 사용할수있는 반복적DP를 사용하였다.

(초밥의 최대 가격이 20000원이여서 여전히 배열선언하기 부담스럽지만 문제에서 주어진 조건인 가격은 100의 배수라는 점을 이용해서 배열의 크기를 200+1까지 줄여나갈 수 있다.)

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/9.%20DP-Technic/SUSHI.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1