Wifi Setup [백준 5864] - python

import sys
input = sys.stdin.readline
INF = 1e11

def BOJ5864():
  N, A, B = map(int, input().split())
  dp = [INF for _ in range(1000001)]
  cows = []
  for _ in range(N):
    curr_cow = int(input())
    cows.append(curr_cow)
  cows.sort()

  curr_wifi = cows[0]
  dp[curr_wifi] = A
  for i in range(1, len(cows)):
    dp[cows[i]] = min(dp[cows[i-1]] + B * (cows[i] -
                      cows[i-1]) / 2, dp[cows[i-1]] + A) 
    # B * (cows[i] - cows[i-1]) 은 이전에 있던 와이파이의 거점을 이동시키는 것과 같다
  if dp[cows[-1]] % 1 == 0:
    print(int(dp[cows[-1]]))
  else:
    print(dp[cows[-1]])


BOJ5864()

 

접근 방법 :

1. 문제가 영어로 되어있었고 문제를 solve한 사람들의 수가 많지 않았어서 약간 위축된 상태로 문제에 접근하지 않았었나 쉽다. 이런 심리상태는 옳지 않다

2. 점화식을 어떻게 짜내냐가 가장 핵심일 것이라 생각해서 점화식 설명을 바로 들어가자
   (와이파이가 커버하는 범위를 늘릴때 인접한 점의 비교를 하는게 점화식 이해에 더 도움이 된다 생각해서 문제의 예시에서 8을 추가하였습니다)

   dp = 각 거점에서 wifi 설치에 따라 커버되는 최소 비용으로 정의해주자

   위의 두 케이스를 비교하면 된다.  wifi를 새로 설치 vs wifi 중심을 옮기고 커버하는 범위를 키우자

dp[cows[i]] = min(dp[cows[i-1]] + B * (cows[i] -
                      cows[i-1]) / 2, dp[cows[i-1]] + A) 
    # B * (cows[i] - cows[i-1]) 은 이전에 있던 와이파이의 거점을 이동시키는 것과 같다

(A는 Wifi 거점을 새로 설치하는 비용이고, B는 wifi가 커버하는 범위를 키우는 것이다)

8에 wifi 거점을 새우는 것 vs 기존의 3.5에 있던 거점을 4로 옮기면서 비용을 추가해주는것의 비교를 해주자.

 

3. 점화식만 알맞게 세우면 문제는 끝이다.

 

장애물 이였던 것 :

1. 아직 dp에 익숙치가 않아서 점화식을 짜는데 어려움이 있었다

 

 

https://www.acmicpc.net/problem/5864

5864번: Wifi Setup