devlog

출처 : https://www.acmicpc.net/problem/24042 풀이 방법주기마다 횡단보도의 신호가 들어온다는 것이 신기했던 문제이다. 현재 위치에서 이동할 수 있는 지역을 계산해 주기 위해 현재 위치에 해당하는 신호가 언제 들어오는지 시간을 체크해 주어야 한다.이를 시간적으로 빠르게 해 주기 위해 그래프의 인접 리스트에 저장할 때 불이 들어오는 시간도 저장해 주었다. (아니면 M시간을 계속 순회해야 함) 그리고 최단 시간 안에 이동해야 하므로 bfs와 우선순위 큐를 사용해서 가장 시간이 적은 것부터 방문해서 처리해 주었다. 다음 노드로 가기 위해 시간계산은 만약 (현재 시간 % m ) 보다 이동할 신호의 시간이 크다면 다음 시간을 cur.time + (next.time - (cur.time..

출처 : https://www.acmicpc.net/problem/2169 풀이 방법해당 문제에서 다른 dp문제와 다르게 고려해야 할 점은 음수 값을 가지는 칸이 있다는 것과 최단 거리가 아니라 가치의 합이 최대이기 때문에 빙 둘러서 오는 것이 답이 될 수 있다는 점이다. 우선 빙 둘러서 오는 것이 답이 될 수 도 있는데 여기서 고려해야 할 점은 한 번 방문한 점은 다시 방문하면 안 된다는 것이다.그렇기 때문에 backtracking을 사용해야함을 알 수 있다. 또한 같은 위치라도 어느 방향에서 오느냐에 따라 해당 위치에서의 최대 값이 달라지므로 3차원 dp를 사용해서 [y][x][dir] 즉 y, x를 dir 방향으로 방문했을 때 최대 값으로 메모리제이션을 했다. 여기서 음수 값이 존재하기 때문에 dp..