[백준] 23090. 난민

newbieski·2021년 10월 15일
0

백준

목록 보기
34/210

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

요약

  • 좌표가 주어질때마다 적절한 점을 골라 거리가(맨하탄거리) 최소인 점 + 그 때의 거리 구하기
  • 최소인 점은 x=0{x = 0} 위에 있고
  • 연속으로 주어지는 좌표마다 처리를 해야함
  • 공식 풀이

접근법

  • x 좌표는 결정에 영향을 미치지 않음. 거리의 합에만 이용함
  • y끼리 모여있을때 적절한 점을 구해야 하는데..
    • 이런류의 문제는 어디선가 풀어보았음
    • 앞에서부터 처리하다가 감소했다가 증가하고..(아래로 볼록 그래프)
    • 삼분 탐색으로 처리하거나
      • 매번 정렬을 해야하니 적절하지 않음
    • 읽어가다가 변화량이 증가하는 곳을 찾거나
      • 매번 다 읽어야하니 적절하지 않음
  • 숫자 3개로 이리저리 엑셀로 그래프를 그려보니 가운데 있는 점이 최소가 되었음
  • 더 생각해보니 다음과 같았음
    • 각 점마다 그래프가 꺾일 것임 => 후보가 되는 점은 꺾이는 점중에 하나 => y 점들
    • 그래프의 모양은 각각의 구간별로 다를텐데 대략 이런 모양일 것임
      • 절대값 처리 : ax{a-x} 이거나 xa{x-a}
      • a100x,b98x,.....c2x,2x+d,...z+100x{a - 100x, b - 98x, ..... c - 2x, 2x + d, ... z + 100x }
      • 기울기가 -100, -98, .... 감소하다가
      • 어느순간 2, 4, .... 증가할 것임
      • 그리고 아래로 볼록 그래프니까 감소하다가 증가하는 어딘가가 "중간"
  • 입력되는 값들의 "중간값"을 처리하는 문제임
profile
newbieski

0개의 댓글