[BOJ 1520]

문제 바로가기 : https://www.acmicpc.net/problem/1520
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

DP로 풀 수 있다.
(0,0)에서 출발하든 (n-1, m-1)에서 출발하든 자윤데 나는 후자를 선택했다.
경계에 벗어나지 않도록 꼭 체크하면서 최종 경로에 닿는 경우 1을 반환할 수 있도록 기저 사례를 설정해주자.
적혀있는 숫자가 더 작은 쪽으로 이동할 수 있다고 설명이 돼있는데 나는 (n-1, m-1)에서 출발하므로 반대로 해줬다.

int dx[] = { -1, 1, 0, 0 }, dy[] = { 0,0,1,-1 };
ret = 0;

for (int i = 0; i < 4; ++i) {
	int nx = x + dx[i], ny = y + dy[i];
	if (OOB(nx, ny)) continue;
	if (board[nx][ny] > board[x][y])
		ret += f(nx, ny);
}

이동할 수 있는 경로면 값을 더해준다는 말 외엔 딱히 설명할게 없다.

계속 새로운 알고리즘을 공부하면서 바쁘게 달렸는데
기본기라고 할 수 있는 완전탐색, DP, DFS, BFS 등이 약하다는걸 최근에 알았다.
사실 이 문제도 2달 전에 DFS로 풀어보려고 끙끙대다 풀지 못하고 때려친게 기억이 난다.
코테를 대비하는 입장이라면 알고리즘을 마구잡이로 공부하기 보다는 (물론 이것도 처음엔 필요하지만)
빈출 유형부터 탄탄히 짚어가며 공부하는게 훨씬 낫겠다는 생각이 든다. 종만북을 최근에 접한게 행운이었다!
DP를 정말 못했는데 감이 생겨가는 것 같아서 다행이다. 좀만 더 열심히 해보자!