- 문제요약
- 충전소가 있고, 충전소는 충전범위와 성능을 가진다.
- 충전범위는 상하좌우로 작용, 성능만큼 충전시켜준다
- 한 BC에 2 명의 사용자가 접속한 경우, 접속한 사용자의 수만큼 충전 양을 균등하게 분배
- BC의 정보와 사용자의 이동 궤적이 주어졌을 때, 모든 사용자가 충전한 양의 합의 최댓값을 구하는 프로그램 작성
- 문제접근
충전소가 최대 8개, 충전범위 최대 4로 완전탐색시 O(8 16 100) 예상된다. 문제는 같은 충전소에 들렀을 때의 중복처리이다. 이 부분에서 많은 시간을 소모했다. 전체 로직은 다음과 같다
- 좌표마다 충전이 가능한 충전소 번호를 map에다 저장, < 좌표, 충전소 번호 벡터 >
- 사용자 좌표를 옮긴다.
- 이동한 좌표에서 충전이 가능한 충전소들을 방문체크한다 (visit[충전소 번호] += 1)
- 이동된 좌표에서 충전 가능한 충전소들의 조합에 따라 얻을 수 있는 충전 양을 비교해서 최대의 충전값을 총 충전량에 더한다.
어려운 문제를 함께 풀어가는 것을 좋아합니다.