[SWEA] 무선충전

피누·2019년 10월 9일
0

문제 링크
코드 보기

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

0개의 댓글