[ICPC 본선 대비 뇌셋] Day 13

백준 16128번 스눕시티 www.acmicpc.net/problem/16128

16128번: 스눕시티

간만에 쉬운문제다. 사실 광고 매칭 문제를 풀다가 막혔고, 어제 계측때문에 포스팅을 계속 못했다. 꾸준히하는게 정말 어려운 것 같다.

[풀이] 몇번 요리조리 돌려보면, A(이전 점), B(이후 점)의 x, y좌표를 각각 2진법으로 볼 생각을 할 수 있다. A, B의 x, y좌표가 가장 많이 겹치는 prefix를 잡으면, A지점에서 prefix지점까지 이동한 후, 다시 B로 이동해야함을 알 수 있다. 각 이동 과정은 2진법 자리수가 올라가면서 최단경로를 보면 된다. 짜려면 귀찮을듯.