내리막 길1 [BOJ] 1520번: 내리막 길 1520번: 내리막 길 풀이 대표적인 동적 계획법 문제라고 한다. 처음엔 어떻게 DP로 풀지??라고 생각했지만 DP라는 방향을 잡고나니 풀기 상당히 쉬워졌다. 기준값: m == 0 && n == 0일 때는 1이다. 점화식…?인지는 모르겠지만 4방향을 돌면서 본인보다 큰지 작은지 확인하면 된다. 나는 탑-다운 방식으로 해서 풀었고 visited 배열까지 써서 풀었지만 사실 dp배열을 -1로 초기화 시키고 분기문을 하나 만들어서 풀면 visited 배열을 만들 필요가 없다고 한다. 참조 코드 #include int dp[501][501], n, m; // dp[i][j]는 (0, 0)에서 (i,j)까지 가는 경우의 수 int map[501][501]; // 입력 저장하는 곳. bool visited[501].. 2018. 5. 31. 이전 1 다음