종만북 알고스팟 문제, FESTIVAL 록 페스티벌 cpp 문제풀이

 

 

오늘은 종만북 첫장에 나오는 알고스팟 문제 중 하나인 록 페스티벌을 풀어보겠습니다. 저는 완전탐색으로 단순하게 푼지라, 더 좋은 방식은 많을 수 있습니다. 언제든 댓글로 의견 부탁드려요. 그럼 종만북 기초문제인 록 페스티벌 문제의 내용부터 보고 가겠습니다. 해당 문제 링크도 아래에 첨부할게요. 참고하세요.

 

종만북 알고스팟문제, FESTIVAL 문제 링크입니다. ▼

algospot.com :: FESTIVAL

 

 

 

---

종만북 알고스팟 기초문제, 록 페스티벌 설명

자세한 설명은 위 내용을 참고해주세요.

요약하자면, 이미 섭외한 팀의 수 이상으로 연속으로 공연장을 빌려야합니다. 공연장을 빌리는 비용은 날마다 상이합니다. 예를 들면, 섭외한 팀이 3명일 경우, 3일 이상(4, 5일도 가능) 공연장을 빌렸을때, 가장 최소한의 평균비용을 내는 경우를 찾는 문제입니다. 

 

 

 

 

테스트케이스의 수는 100 이하입니다. 대여할 수 있는 날들의 수는 1000, 섭외한 공연팀의 수는 최대 1000입니다.

해당 문제는 완전탐색을 통해서 풀어도 1초 미만의 속도로 문제를 풀 수 있습니다.

주의 할 점은, 해당 문제는 소수점까지 판별을 하며, 소수점 7자리 까지는 연산결과를 출력해주어야 문제없이 통과할 수 있습니다. 그럼 바로 cpp 언어로 문제 풀어보겠습니다.

 

 

 

---

종만북 알고스팟 기초문제, 록 페스티벌 cpp 풀이

헤더를 먼저 추가합니다. cpp 표준입출력 헤더, vector 헤더를 추가했습니다. 본 문제에서 사실 algorithm 헤더는 필요하지 않습니다.

10행) 이제 메인함수로 바로 가보겠습니다. 테스트케이스의 수, C를 입력받았습니다.

 

 

 

 

테스트케이스를 반복수행할 반복문은 while을 사용해주었습니다.

13 ~ 15행) 각 테스트케이스마다 N, L을 입력받습니다. ans 변수에는 최소비용을 저장할 예정이기에, 나올 수 있는 최댓값 이상의 값을 임의로 넣어둡니다. 이후 각 날 마다의 공연장 대여 비용을 G 벡터에 저장해주었습니다.

16 ~ 25행)  앞서 서두에 말씀드렸듯이 해당문제는 완전탐색(브루트포스)을 통해 풀어도 문제없습니다. 그래서 완전탐색을 수행해서 풀었습니다.

0 ~ N 범위의 날 들을 하나하나 탐색하며 처음 공연장을 대여하는 시작점이 i인 모든 경우의 수를 돌려봅니다. 이때 최소 대여일이 K ~ 시작점으로 최대한 빌리는 경우까지 모두 확인하여 모든 경우의 수에 대한 최소 평균 공연장 대여비용을 구합니다. 이때 평균 비용은 반드시 소수점 7자리 이상을 연산 가능한 double 타입 연산을 수행해주었습니다.

 

 

 

 

마지막 정답 제출은 소수점으로 틀리는 것을 방지하기 위해 넉넉하게 소수점 9자리까지 출력하도록 했습니다.
관련 의견 언제든 환영해요. 댓글 부탁드립니다.

그럼 모두들 즐거운 코딩 되시길 바랍니다. 수고하세요.