x,y 위치의 풀을 깎고 나면 t초 후에 다시 깎아야할만큼 자란다.
그리고 FJ는 항상 효율적으로 움직이기 때문에 같은 위치를 t초가 지나기 전에 깎지 않는다.
FJ의 움직임이 N번 주어졌을 때 가능한 t중 최대값을 구하는 문제다.
해법
움직이면서 생기는 교차점이 있으면 교차하는데까지 걸리는 시간을 구하고 이 시간중 최소값을 구하면 된다.
N이 100까지이고 한번 움직이는데 최대 10번 움직이기 때문에 한칸씩 움직이면서 map에 타이밍을 저장한다.
같은 위치를 또 방문한다면 현재시간과 저장된 시간을 비교하고 ans를 갱신한다.
#include <stdio.h> #include <algorithm> #include <map> using namespace std; map<pair<int, int>, int> s; int main() { int n, x = 0, y = 0, cnt = 0, ans = 100000, dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 }; scanf("%d", &n); s[{x, y}] = 0; while (n--) { char d; int c; scanf(" %c %d", &d, &c); if (d == 'N') d = 3; else if (d == 'E') d = 0; else if (d == 'W') d = 1; else d = 2; while (c--) { x += dx[d]; y += dy[d]; cnt++; if (s.count({ x,y })) ans = min(ans, cnt - s[{x, y}]); s[{x, y}] = cnt; } } printf("%d\n", ans == 100000 ? -1 : ans); return 0; } | cs |
'BOJ' 카테고리의 다른 글
| 14174 Block Game (0) | 2018.11.10 |
|---|---|
| 14173 Square Pasture (0) | 2018.11.10 |
| 11977 Angry Cows (Bronze) (0) | 2018.11.10 |
| 14457 Cow Tipping (0) | 2018.11.10 |
| 1909 냄새 싫어 (0) | 2018.11.07 |