Simulation2 백준 14503 : 로봇 청소기 (Gold 5) 문제 문제 해석 시뮬레이션 문제. 문제에서 말하는 그대로 구현하면 됩니다. 그러나 문제 설명에서 후진하는 시점이 조금 애매한데 두 번째 예제처럼 출력이 나오려면 네 방향 모두 청소할 수 없음을 알아챈 순간 왼쪽으로 회전하지 않고 후진해야 합니다. 통찰 구현 문제이기 때문에 통찰이 필요없습니다. 시간 복잡도 4 * n * m = 4 * 50 * 50 = 10000 < 20억 (2초) n * m 만큼의 칸에서 4방향 모두 탐색 풀이 /** * @template file author kadrick (kbk2581553@gmail.com) * * author:amkorousagi (hasmi5452@gmail.com) */ #include using namespace std; #define fastio \ io.. 2022. 10. 22. 백준 13460 : 구슬 탈출 2 (Gold 1) 문제 문제 해석 시뮬레이션. 일반적인 미로 문제의 변형. - 한번 출발한 방향으로 막힐 때까지 간다. - 동시에 두 구슬이 움직인다. - 파란 구슬이 떨어지면(출구에 도달) 안된다. 위 세가지만 유의하면 됩니다. 통찰 DP나 그리디와 달리 통찰이 필요 없습니다. 문제에서 요구하는 그대로 구현하면 됩니다. 처음에는 board전체를 복사하고 R과 B를 실제로 적는 식으로 하였는데 복사에 너무 많은 시간이 들어서(n*m = 10*10) 보드는 그대로 두고 구슬의 위치만 기록하는 식으로 변경하였습니다. 시간 복잡도 시간 복잡도 = 4^10*max(n, m) = 상하좌우 * 깊이 10까지 bfs * 한번 기울일 때 최대 이동하는 거리 max(n, m) n, m이 10일 때, 시간 복잡도는 4^10*10 = 2^1.. 2022. 10. 22. 이전 1 다음
