백준 16128번 스눕시티 www.acmicpc.net/problem/16128
16128번: 스눕시티
첫 줄에 땅의 크기를 의미하는 정수 N과 일일 퀘스트가 주어지는 날의 수를 의미하는 정수 M(1 ≤ N ≤ 40, 1 ≤ M ≤ 100,000)이 주어진다. 땅의 크기는 2N × 2N임에 유의하라. 둘째 줄에 최초의 꽃밭의
www.acmicpc.net
간만에 쉬운문제다. 사실 광고 매칭 문제를 풀다가 막혔고, 어제 계측때문에 포스팅을 계속 못했다. 꾸준히하는게 정말 어려운 것 같다.
[풀이] 몇번 요리조리 돌려보면, A(이전 점), B(이후 점)의 x, y좌표를 각각 2진법으로 볼 생각을 할 수 있다. A, B의 x, y좌표가 가장 많이 겹치는 prefix를 잡으면, A지점에서 prefix지점까지 이동한 후, 다시 B로 이동해야함을 알 수 있다. 각 이동 과정은 2진법 자리수가 올라가면서 최단경로를 보면 된다. 짜려면 귀찮을듯.
'PS > 2020 ICPC 본선 대비 뇌셋' 카테고리의 다른 글
| [ICPC 본선 대비 뇌셋] Day 15 (0) | 2020.11.04 |
|---|---|
| [ICPC 본선 대비 뇌셋] Day 14 (0) | 2020.11.03 |
| [ICPC 본선 대비 뇌셋] Day 12 (4) | 2020.10.29 |
| [ICPC 본선 대비 뇌셋] Day 11 (0) | 2020.10.28 |
| [ICPC 본선 대비 뇌셋] Day 10 (0) | 2020.10.27 |
