반응형 DP6 BOJ 2579 - 계단 오르기 / C++ 문제 링크 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 풀이 DP를 이용하여 푼다. 우선 1번 계단과 2번 계단의 최댓값은 모든 계단을 밟으면 되므로 그대로 초기화해준다. 3번 계단부터는 경우가 여러 개로 나뉘어진다. (1). 1번 계단 -> 3번 계단 (2). 2번 계단 -> 3번 계단 (1)번 경우에는 DP[1] + arr[3]이 될 것이고 (2)번 경우에는 arr[2] + arr[3]이 될 것이다. DP[2]에는 arr[1] + arr[2.. 2022. 2. 28. 프로그래머스 - 땅따먹기 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 문제 풀이 DP를 적용하여 풀면 된다. 주의할 점은 바로 직전의 열이 겹치면 안된다는 것이며 한 행은 항상 4열이다. 따라서, 점화식을 세울 때 해당 행에서 가장 큰 수를 더하되 열이 겹치면 continue해준다. 소스 코드 #include using namespace std; int solution(vector land) { .. 2021. 11. 21. 이전 1 2 다음 반응형