Problem Solving/DP 썸네일형 리스트형 BOJ 2602 - 돌다리 건너기 문제 링크https://www.acmicpc.net/problem/2602 문제 해결1. " 한 방향으로 이동 + 모든 경우의 수 " 에서 Dynamic Programming으로 해결 2. dp[i][j][k] = i (천사 또는 악마) 행, j (돌다리) 열을 밟았을 때 두루마리 속 k번째 문자를 밟은 경우의 수. 3. Top-down 형태로 풀려고 애썼다. 주의할 점 || 생각해볼 점1. Dp 배열을 만드는 것이 어려웠다. 완전 탐색 하면서 놓치지 않아야 할 정보를 담아야한다. 2. 기저 조건을 설정하는 것이 익숙하지가 않았다. 가령 최대 인덱스가 k라면, k+1에서 기저 조건을 수행. ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1149 - RGB거리 문제 링크https://www.acmicpc.net/problem/1149 문제 해결1. dp[i][1~3] = i번째 집에 Red or Green or Blue를 칠할 때 드는 비용. 2. 이웃한 집에는 같은 색을 칠할 수 없고, N번째 집까지 칠했을 때 최소 비용을 구한다. 주의할 점1. dp라는 배열을 이용해서 바로바로 저장하면서 값을 구할 수 있다. 2. 이웃한 집의 색은 이전 집만 겹치지 않게 구현한다면 결과적으로 양 옆으로 겹치지 않게 된다. ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 11060 - 점프 점프 문제 링크https://www.acmicpc.net/problem/11060 문제 해결1. DP[i] = i번째에서 끝까지 이동하는 최소 이동 횟수. 주의할 점1. 처음에 DP 배열의 모든 값들을 큰 값들로 초기화한다. 2. 매번 값을 확인해줄 때, 최소값으로 갱신해야한다. 3. input이 1이 되면 0을 출력하는 지 확인한다. ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 이전 1 2 3 4 다음