728x90 Baekjoon/[Code.plus] 알고리즘 기초 1／269 [BOJ/백준] 1932 정수 삼각형 ● [문제번호 1932] 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 ● 풀이 과정 : DP 풀이과정 (Bottom - Up) 1. 테이블 정의하기 → dp[row][col] : 맨 위층에서 row행 col열 까지 경로의 최대합 2. 점화식 찾기 → 문제에서 그려진 예각삼각형이 아닌 입력할때 처럼 생긴 직각삼격형으로 생각한다. 그러면 맨 위층에서 내려갈때(row가 커질 때) 자신과 동일한 col이거나 자신보다 1 큰 col+1 로 내려갈 수 있다. dp[row.. 2021. 8. 5. [BOJ/백준] 2156 포도주 시식 ● [문제번호 2156] 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 ● 풀이 과정 : DP 풀이과정 (Bottom - Up) 1. 테이블 정의하기 → dp[연속해서 마신 수][index] : index까지 마신 포도주의 최대 양 2. 점화식 찾기 → dp[연속해서 마신 수][index] 값은 연속해서 마신 수 : 0 → 이전 index의 연속해서 마신 수가 0, 1, 2 중 최대 연속해서.. 2021. 8. 5. [BOJ/백준] 9465 스티커 ● [문제번호 9465] 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 ● 풀이 과정 : 1309 동물원 문제 와 매우 비슷하다. : DP 풀이과정 (Bottom - Up) 1. 테이블 정의하기 → dp[row][col] : row행 col열까지 스티커 최대 점수 (row가 0인 경우는 그 col열은 스티커 사용X) 2. 점화식 찾기 dp[0][col] = max( dp[0][col .. 2021. 8. 5. [BOJ/백준] 11057 오르막 수 ● [문제번호 11057] 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 ● 풀이 과정 : DP 풀이과정 (Bottom - Up) 1. 테이블 정의하기 → dp[digit][last] : 자릿수(digit)이고 1의 자리수(last)로 만들어질 수 있는 총 경우의 수 2. 점화식 찾기 → 이전 자릿수보다 큰 다음 자릿수 경우의 수에 이전 자릿수 경우의 수를.. 2021. 8. 5. 이전 1 2 3 4 5 6 ··· 18 다음 728x90
