본문 바로가기

Algorithm283

[BOJ]17406번: 배열 돌리기 4 www.acmicpc.net/problem/17406 시뮬레이션 문제입니다. 주의해야 할 특이사항은 없는 거 같습니다. 1. parameter로 2개의 좌표를 받습니다. (좌측 상단, 우측 하단) 2. 좌측상단, 우측하단 2개의 좌표를 기준으로 4개 꼭지점 좌표를 구합니다. 3. 구역을 4개로 나눠 (9시 방향, 12시 방향, 3시 방향, 6시 방향) 한 칸씩 시계방향으로 밀어줍니다. 4. 좌측상단 좌표 (x,y) -> (x+1,y+1)로 갱신, 우측하단 좌표 (x2,y2) -> (x2-1,y2-1)로 갱신 후 1번 과정을 반복 회전을 위한 루프 횟수는 맨 처음에는 2*S만큼 돌고 좌측상단, 우측하단 좌표가 갱신되어 재귀가 생길 때 마다 2칸씩 줄어듭니다. 문제를 시뮬레이션하면 고려해야할 부분들에 대해 .. 2020. 10. 12.
[BOJ]1800번: 인터넷 설치 www.acmicpc.net/problem/1800 justicehui님의 풀이를 보고 해결했습니다. (justicehui.github.io/usaco/2019/07/12/BOJ1800/) 단순히 DFS를 돌려버리면 터지므로 다익스트라 + 결정 문제로 바꿔서 해결합니다. "특정 가중치 이하의 간선으로만 경로를 구성할 수 있는가?"를 결정하는 문제로 특정 가중치가 넘는 간선에 대해서는 1의 가중치를 주고 특정 가중치가 넘지 않는 간선에 대해서는 0에 가중치를 주어 다익스트라를 돌립니다. 만든 최단 경로가 K 이하의 가중치로 도달가능하다면 이 값은 가능한 값으로 저장해놓고 mid를 더 줄여서, 더 작은 가중치로 다시 연결 시켜봅니다. 만든 최단 경로가 K 이하의 가중치로 도달이 불가능하다면 mid를 올려서 .. 2020. 10. 10.
[BOJ]19237번: 어른 상어 www.acmicpc.net/problem/19237 시뮬레이션 문제입니다. 이 문제를 풀 때 가장 중요한 것은 문제 시나리오를 쪼개는 방식이라고 생각합니다. 제가 해결한 순서는 아래 4가지 순서로 문제를 나눠서 해결했습니다. 1. 모든 상어 이동 2. (상어가 이동을 모두 마쳤으니) 기존에 상어가 냄새뿌려놓았던 칸 count-- 3. 상어가 이동 후 겹치는 칸이 있는지 check -> 겹치면 상어 kill 4. 상어가 새로 이동한 칸에 냄새 뿌리기 N제한이 작기 때문에 시뮬레이션으로 구현만 하면 됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ19237.cc 2020. 10. 10.
[BOJ]19238번: 스타트 택시 www.acmicpc.net/problem/19238 시뮬레이션 문제입니다. N제한과 M제한이 크지 않으므로 다음 손님 탐색과, 손님 이동 모두 BFS로 해결해도 됩니다. 그래도 O(N^2 * M)이 O(20^4) 입니다. 한 가지 빼먹기 쉬운 조건이 "택시가 시작하는 위치와 손님의 시작위치가 같은 경우"가 있다는 것입니다. 이 경우에는 거리를 0으로 하고 처리하면 됩니다. 저는 이 조건 놓쳐서 계속 탐색 시작 거리를 1로 놓고 했다가 많이 틀렸었네요. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ19238.cc 2020. 10. 10.

티스토리툴바