[2579]階段を登る
🔗 質問リンク
https://www.acmicpc.net/problem/2579
🔍 問題の説明
階段を登るゲームは階段の下の起点から階段の先端の終点までのゲームです.図1>に示すように、階段ごとに一定の点数が書かれており、階段を踏むと階段の点数が得られます.
<図2>に示すように、始点から、第1、2、4、6段の階段を歩いて終点に着き、合計10+20+25+20=75点となる.
階段を登るには以下のルールがあります.
階段は一度に1段または2段上がることができます.つまり、階段に沿って、次の階段を上ったり、次の階段を下りたりすることができます.
連続した3つの階段を踏んではいけない.しかし、起点は階段には含まれていません.
最後に着いた階段は必ず踏まなければなりません.
そのため、最初の階段に沿って、2番目か3番目の階段を歩くことができます.しかし、最初の階段を踏んで4番目の階段を登ったり、最初の階段、2番目の階段、3番目の階段を連続して踏んだりすることはできません.
各段階の点数を与える場合は、ゲームの総点数の最値を求めるプログラムを作成します.
⚠▼制限
階段の個数は300以下の自然数です
階段に書いてある点数は10000以下の自然数です
🗝 プール(言語:Java)
DPで簡単に解決できる問題ですが、「連続した3つの階段を足元に踏み込むことができない」という条件の一つで悩む問題です.この条件を解決する方法は、ステップごとに最大値を持つ2 D配列を作成し、0番目の要素は前のステップから、1番目の要素は前のステップから、2つの状況を最後まで更新することです.この法則性を見つけてこそ簡単に解くことができる.また、1段目は前の段を踏まずに[0]の2番目の位置に置くことで儀式が成立します.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
private static int findMaxValue(int n, int[] arr) {
int[][] matrix = new int[n+1][2];
matrix[1][0] = arr[1]; // 첫 계단은 1가지 경우뿐
for (int i = 2; i <= n; i++) {
// 0은 바로 앞 계단을 밟지 않는 경우, 전전의 계단의 두개의 경우 모두 가능
matrix[i][0] = arr[i] + Math.max(matrix[i-2][0], matrix[i-2][1]);
// 1은 바로 앞 계단을 밟는 경우, 그래서 전계단이 전전계단을 밟지 않는 경우[0]만 해당
matrix[i][1] = arr[i] + matrix[i-1][0];
}
return Math.max(matrix[n][0], matrix[n][1]);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n+1];
for (int i = 1; i <= n; i++)
arr[i] = Integer.parseInt(br.readLine());
br.close();
System.out.println(findMaxValue(n, arr));
}
}
Reference
この問題について([2579]階段を登る), 我々は、より多くの情報をここで見つけました https://velog.io/@shiningcastle/2579-계단-오르기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol