-
https://www.acmicpc.net/problem/1890
https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201890
해당 문제는 map가 주어졌을 때 0,0에서 n-1, n-1까지 가는 경우의 수를
구하는 문제다.
이동은 map에 주어진 수만큼 이동 가능한데 방향이 오른쪽 또는 아래로만 가능하다
즉 3이면 오른쪽으로 3칸 or 아래로 3칸 이동이 가능하다.
처음에 bfs를 이용해서 문제를 풀었는데 메모리 초과가 났었고, 방문을 통해
메모리 초과를 해결했더니 시간 초과가 발생하였다.
그래서 찾아보던 중 dp를 같이 써야 하는 걸 알게 되었고,
dp를 이용해서 값을 저장해 주며 만약 도착점으로 가면 continue를 통해 중복으로
더해지는 걸 막아주었다.
728x90'알고리즘 > Baekjoon' 카테고리의 다른 글
Baekjoon 1058 친구 JAVA (0) 2021.11.15 Baekjoon 14500 테트로미노 JAVA (0) 2021.11.15 Baekjoon 3273 두 수의 합 JAVA (0) 2021.11.15 Baekjoon 11054 가장 긴 바이토닉 부분 수열 JAVA (0) 2021.11.15 Baekjoon 2583 영역 구하기 JAVA (0) 2021.11.15 댓글