# DP
[BOJ] 12865 평범한배낭
dpi = Math.max(dpi-1, dpi-1 + v)dpi-1 값을 참조해야한다. dpi값은 갱신이 안되어있을 수 있기 때문이다.(당연함)
[백준:1937] 욕심쟁이 판다
n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이
백준 11049 행렬 곱셈 순서 (C++)
11049번: 행렬 곱셈 순서dp를 활용한 분할 정복 문제이다. 이 문제의 핵심은 점화식을 잘 세우는 것이다. 먼저 행렬의 곱 방식을 보자. 행렬 A (2,3), 행렬 B (3,4)가 있다고 할 때, 둘의 곱은 (2,4)가 되고 곱샘 횟수는 2 X 3 X 4가 된다.
[백준 / 실버2] 1912 연속합 (Java)
문제 보기 사용한 것 구간의 최대 합을 구하기 위한 bottom-up 풀이 방법 arr에 숫자 입력 받음 (인덱스 1부터) 인덱스 1부터 구간을 계속 더하거나 새로 시작하거나 둘 중 큰 값 선택 dp 중에 가장 큰 값 선택 코드
Leetcode - 64. Minimum Path Sum
2차원 배열이 주어지고 좌상단에서 우하단으로 이동할때 가능한 경로중 최소비용은? (이동시 경로의 값을 더함)dp문제
[백준 1103] 게임
문제 출처사용 언어: Java구상현재 위치에서 상하좌우로 움직였을 때의 숫자를 확인하여 그 중 가장 작은 숫자를 택하기무한으로 움직이는지 확인하기 위해 방문 여부 기록 (visited 배열)→ 무한으로 움직인다면 게임을 그 자리에서 종료시키고 -1 출력DP 알고리즘을
백준 :: 쉬운 계단 수 <10844번>
dpi-1의 끝자리 +1, -1 해서 다음 계단 수 생성 가능단, 끝자리가 0일 때는(min) -1로 내려갈 수가 없고 9일 때는(max) 10으로 올라갈 수가 없다.업로드중..dpi에 0의 갯수는 이전 dpi-1 1의 갯수와 동일하다. (1에서 -1 한게 0이 되
[백준 / 실버3] 2193 이친수 (Java)
문제 보기 사용한 것 이친수의 개수를 구하기 위한 bottom-up 풀이 방법 이친수가 될 수 있는 경우는 다음과 같다. 이번 차례에 0이 오는 경우는 모두 가능 -> dp[i - 1] 이번 차례에 1이 오는 경우는 앞이 0이 아닐 때 가능 -> dp[i - 2] 코드
Lv2. 3 x n 타일링
코딩테스트 연습 > 3 x n 타일링홀수인 경우에는 직사각형을 채울 수 없다.memo 리스트를 0으로 초기화하고, n이 2인 경우에는 3, n이 4인 경우에는 11로 초기화한다.2중 for문을 돌면서 memo\[i] 를 업데이트 한다.. 6부터 n까지 for문을 돌면서
14852번 타일 채우기3
2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자.첫째 줄에 N(1 ≤ N ≤ 1,000,000)이 주어진다.첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.일반적인 타일 채우기 형태이다.
2133번 타일 채우기
3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.첫째 줄에 경우의 수를 출력한다.N이 홀 수 일때는 칸을 채울 수 없다. N-2 에서 새로운 형태가 3개 등장하고N-4 부터는 저렇게 생겼지만
백준 9251 LCS (C++)
9251번: LCS동적 프로그래밍을 활용한 최장 공통 부분 수열 구하기 문제이다. 사실 이 문제는 LCS 알고리즘으로 많이 알려져있는 문제이다. 그렇기에 어렵지않게 풀 수 있었다. 문자열의 크기만큼 반복문을 돌면서 같은 문자열을 발견하게 되면, 해당 위치의 LCS 배열
내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.현재 제일
