본문 바로가기

알고리즘74

DP 풀이방법 5가지 정리 - 백준 11048번 : 이동하기 Python 파이썬 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 방법1 : Top-Down 문제가 점점 작아지는 방식으로 접근 목적지까지 어떻게 왔는지에 대해서 생각하며 접근 결론에 도달하기까지의 과정에 대해 생각하며 접근 dp[i][j] : (1,1)에서 시작하여 (N,M)까지 가는 중에 (i, j) 까지 갔을 때의 가진 최대 사탕의 수 왼쪽에서 온 경우 : (i, j-1)에서 온 경우 왼쪽 위에서 온 경우 : (i-1, j-1)에서 온 경우 .. 2022. 1. 11.
백준 11048 : 이동하기 - 파이썬 Python https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 생각하기 가져올 수 있는 사탕의 최대를 구하는 것이기 때문에 생각을 했다 DFS로 모든 경우를 다 해봐? 규칙 같은 것을 찾아서 DP로 만들어볼까? DFS로 풀면 시간초과가 발생할 것 같다는 생각이 들었다. 1000 * 1000 인데 각 경우가 3가지 경우만 고려하더라도 각 칸은 세가지의 경우로 뻗어나갈 가지수를 가지고 있으므로 최대 가로 세로 1000칸이라면 3000000의 가지수.. 2022. 1. 6.
백준 16954번 : 움직이는 미로 탈출 - 파이썬 Python https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 생각하기 시간이 1초씩 지남에 따라서 1. 욱제가 이동하고 2. 벽이 바뀐다 시간이 1초씩 바뀌는 것을 단계별로 나타내기 위해서 bfs를 사용한다 구현하기 큐에다가 row, col 좌표, 흘러간 시간을 묶어서 append 시킨다 큐에서 popleft시키면서 흘러간 시간이 바뀐 경우 체스판의 벽을 한줄씩 내린다 주의할 점 1 체스판의 벽이 한줄씩 내려가다보면 가장 위쪽행은 모두 벽이 없는.. 2022. 1. 1.
백준 14442번 : 벽 부수고 이동하기2 - 파이썬 Python https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 생각하기 bfs 방식을 통해서 가장 먼저 목적지에 도착하면 해당 카운트를 return 하는 방식으로 생각 벽을 부순 횟수 K번에 대한 각각의 visited를 따로 구별해서 표현해야 visited[횟수][row][col] 벽 부순 횟수에 따라 row와 col에 방문한 적이 있는가 체크하여 방문하였으면 중복해서 방문하는 케이스를 줄인다. 구상하기 큐를 사용하여 bf.. 2021. 12. 26.

티스토리툴바