프로그래머스 미로 탈출 명령어 - C++ 풀이
1. dp(r, c, k): (r,c)에서 정확히 k번의 이동으로 도착지점에 도달할 수 있는지 여부 2. dp(r, c, k): dp(nr, nc, k-1) = 1인 인접한 칸 (nr, nc)가 하나라도 있는가 3. 이동방향에 대한 우선순위는 d, l, r, u이다. 1. dp(r, c, k): (r,c)에서 정확히 k번의 이동으로 도착지점에 도달할 수 있는지 여부 dp(r, c, k)를 위와 같이 정의하자. R = C = 50, K = 2500이므로 구해야 하는 상태값의 개수는 50*50*2500개. 제한 시간 내에 모두 구하기 충분하다. 기저 사례는 k=0인 경우로 이때 위치한 칸이 도착지점인지 판단하면 된다. 2. dp(r, c, k): dp(nr, nc, k-1) = 1인 인접한 칸 (nr, nc..
2023. 7. 22.
백준 1309번 동물원 - C++ 풀이
1. dp(idx, prev) : (idx-1) 번째 행의 상태가 prev일 때 idx번 행~마지막까지 채우는 방법의 수 2. prev = 0 이면, dp(idx, prev) = dp(idx+1, 0) + dp(idx+1, 1) + dp(idx+1, 2) 3. prev > 0 이면, dp(idx, prev) = dp(idx+1, 0) + dp(idx+1, 3-prev) 1. dp(idx, prev) : (idx-1)번째 행의 상태가 prev일 때 idx번 행~마지막까지 채우는 방법의 수 dp(idx, prev)를 위와 같이 정의하자. 사자가 세로로 붙어있을 수 없으므로 prev값이 필요하다. 이때 사자가 가로로 붙어있을 수 없으므로 한 행 내의 사자 상태는 아예 없거나, 오른쪽 칸에만 있거나, 왼쪽 칸에..
2022. 9. 22.
