[伯俊]No 2156-ワイン試飲(JAVA)
10624 ワード
3つのワインを連続的に飲めない条件はhttps://www.acmicpc.net/problem/2579と似ている.私はその質問に答えている間に知らなかったので、放っておいて、ついでにこのタイプの質問を知りたいのでブログ記事を書きました.
まず問題で与えられた条件.
ワインを3つ続けて飲めません。
つまり.
連続
max[i] = max[i-1]
/0連続?Xmax[i] = wine[i] + max[i-2]
/1連続?XOmax[i] = wine[i] + wine[i-1] + max[i-3]
/2個の連続XOOいいですよ.
0個連続で、
i-1
とi-2
でワインを飲んでも飲まなくても.したがって、max[i]はmax[i-1]の値に等しい.1個連続の場合、
i-1
は必ずしも飲む必要はありません.しかしi-2
は関係ありません.したがって、max[i]は現在連続した値であるため、wine[i]にmax[i-2]を加算する.2つ連続の場合は必ず
i-1
、必ずしもi-2
を飲む必要はありません.したがって、max[i]=wine[i]+wine[i-1]+max[i-3]となる.✔この3つの条件の中で最大の値は[i]を占めます。
また、イグニッション式ではi-3に近いので、ループ文の前に初期値を設定!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class No2156_포도주시식 {
static int[] wine = new int[10001];
static int[] max = new int[10001];
static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
for (int i=1;i<=n;i++) {
wine[i]=Integer.parseInt(br.readLine());
}
max[1]=wine[1];
max[2]=wine[1]+wine[2];
max[3]=Math.max(max[2],Math.max(wine[3]+wine[1],wine[2]+wine[3]));//초기값 세팅
for (int i=4;i<=n;i++) {
max[i]=Math.max(Math.max(max[i-1],wine[i]+max[i-2]),wine[i]+wine[i-1]+max[i-3]);
}
System.out.println(max[n]);
}
}
に感銘を与える
このように,dp問題に
'몇개 이상 연속하지 못하는'
の条件がある場合,この方法で近づくことが分かった.明日は階段を登る問題も解決しなければなりません.頑張ってください.
Reference
この問題について([伯俊]No 2156-ワイン試飲(JAVA)), 我々は、より多くの情報をここで見つけました https://velog.io/@kekim20/백준-No2156-포도주-시식JAVAテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol