2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net

계단오르기 문제입니다. 이 문제는 이전에 풀었던 포도주 문제와 유사했던 문제였습니다.
1,2,3번째 일경우에는 계단 오르기 규칙에 맞게 풀면되었고 나머지 경우에는 무조건 마지막 계단수를 밟아야 한다는 규칙에 따르도록 마지막 계단 + 마지막 전 계단 + 마지막 계단 -3 계단 수의 최대값을 구한 값 혹은 마지막 계단 + 마지막 계단 + 마지막 계단 -2 위치에서의 최대값 둘중 더 큰 값을 구해나가면 됩니다.
package com.company;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
int number[] = new int[t];
int dp[] = new int[t];
for (int i = 0; i < t; i++) {
number[i] = Integer.parseInt(br.readLine());
}
dp[0] = number[0];
if(t>1){ dp[1] = number[0]+ number[1];}
if(t>2){dp[2] = Math.max(number[0],number[1]) + number[2];}
for(int i=3; i<t; i++){
dp[i] = Math.max(dp[i-2] +number[i] ,dp[i-3] + number[i]+number[i-1]);
}
System.out.println(dp[t-1]);
}
}
DP - 2156(포도주 시식) :: 꿈을 보는 개발자 (tistory.com)
DP - 2156(포도주 시식)
2156번: 포도주 시식 (acmicpc.net) 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을
islandofdream.tistory.com
해당 문제와 연계해서 풀어도 좋은 문제입니다.
'C++ > DP' 카테고리의 다른 글
DP-2133(타일 채우기) (0) | 2021.01.16 |
---|---|
DP-1699(제곱수의 합) (0) | 2021.01.16 |
DP- 1912(연속합) (0) | 2021.01.13 |
DP - 11054 (가장 긴 바이토닉 부분 수열) (0) | 2021.01.09 |
DP -11053 , 11055 , 11722 (0) | 2021.01.09 |