Will the Guru

Category: Dynamic Programming

  • (KOR) 포도주 시식

    Problem – ⭐️⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/2156 Solution Key Points 계단오르기 문제와 비슷해보였으나, 마지막 잔을 반드시 선택할 필요가 없었던 점에서 차이가 있었다. 풀이방법 dp[n][k] = n번째 와인잔을 골랐을 때, 그것이 k번 연속되었을 경우 마실 수 있는 최대 포도주 양. dp[n][2] 가 아닌 dp[n+1][3]으로 설정한 이유는, dp[i][1]를 구할 때 i-2를 참조해야하므로 dummy 값을 추가해준…

  • (KOR) 쉬운 계단 수

    Problem – ⭐️⭐️⭐️ https://www.acmicpc.net/problem/10844 Solution Key Points 2차원 배열을 이용한 다이나믹 프로그래밍이 핵심이였던 문제. 점화식이 바로 떠오르지 않을 경우, f(1), f(2), f(3), .. 하나씩 직접 해보면서 점화식을 도출해내는 것이 좋다. 풀이 방법 dp[n][k] = 끝자리가 k 인 n 자리 수 끝자리가 0, 9 인 경우는 예외적인 경우로 따로 핸들링해준다 int…

  • (KOR) 계단 오르기

    Problem – ⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/2579 Solution Key Points 점화식을 떠올리는 과정이 핵심이였던 문제. f(0), f(1)에서 시작해서 f(n)까지 점차 규칙을 찾는 과정이 필요했다. 풀이방법 f(n, k) = n번째 계단에 오를 때 얻을 수 있는 최대 점수. 이 때, n번째 계단은 k번 연속된 계단을 오른 경우이다. g(n) = n번째 계단의 점수 f(n, 0)…

  • (KOR) 정수 삼각형

    Problem – ⭐️⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/1932 Solution Key Points Using brute-force to calculate all possible solutions resulted in duplicate calculations, causing timeout. To avoid timeout, have to use dynamic programming either Bottom-Up or Top-Down