목록2024/10/07 (1)
미소를뿌리는감자의 코딩
[백준 2024/10/07] 10844번 쉬운 계단 수
1. 문제https://www.acmicpc.net/problem/10844 2. 접근 방법이번 문제의 경우, 처음에 dfs와 memoization으로 접근하였다.하지만, 약점인 dp를 극복하기 위해 고른 문제인 만큼 다시 dp로 접근하려고 노력 하였다.dfs의 길이 보이니, 역으로 dp를 생각하는 것이 까다로웠다. 점화식을 세워보았다.f(i-1, n) + f(i+1, n) = f(i, n+1) 1 -> 0, 2가 올 수 있고, 2 -> 1, 33 -> 2, 44 -> 3, 55 -> 4, 66 -> 5, 77 -> 6, 8 즉 앞 뒤로 값이 올 수 있으므로, 위와 같은 점화식을 세워주었다. 이제 n이 1일 때의 식을 세워주었다.2차원 배열로 보았을 때, 아래와 같은 모양을 나타낸다. 0 1 ..
코딩 테스트/백준
2024. 10. 7. 21:35