리듬 게임의 한 곡에 노트 n개가 차례로 나온다. i번째 노트의 점수는 a_i이고, 음수일 수도 있다. 노트마다 칠지 그냥 보낼지 고른다. 바로 앞 노트도 쳤다면 이번 노트는 콤보를 잇는다. 콤보에서 첫째로 친 노트는 점수의 1배, 둘째로 친 노트는 2배, 셋째와 그 뒤로 친 노트는 모두 3배를 얻는다. 노트를 하나 보내면 콤보가 끊기고, 그다음에 치는 노트는 다시 콤보의 첫째(1배)가 된다. 첫 노트는 늘 콤보의 첫째다. 얻는 점수는 친 노트들이 얻은 점수의 합이다. 하나도 치지 않으면 0점이다. 첫 줄에 n, 둘째 줄에 a_1 … a_n이 빈칸으로 띄워 주어진다. 얻을 수 있는 가장 큰 점수를 출력하라.
5 -1 5 3 -10 4
22
3 -5 -2 -7
0
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
음수 노트라도 쳐서 콤보를 이어야 뒤 노트가 3배를 받을 수 있어서(5 5 -1 5 5는 모두 치면 42점, -1만 보내면 30점), 0보다 큰 노트만 치는 욕심 풀이는 틀려요.
노트 하나를 지날 때마다 "방금 보냈다·콤보 첫째·둘째·셋째 이후" 네 상태의 가장 좋은 점수를 이어 가는 동적 계획법이면 n번 만에 끝나요.
첫째 함정은 상태를 바꾸는 차례예요.
새 값은 모두 이전 노트의 값으로 계산해야 해서, 하나씩 바로 덮어쓰면 c2가 이미 바뀐 c1을 써요.
Python은 skip, c1, c2, c3 = …, JS·TS는 배열 구조 분해 [skip, c1, c2, c3] = [...], C#은 튜플 (skip, c1, c2, c3) = (...)로 한꺼번에 바꿀 수 있어요.
Java·C·크레이콘에는 이런 동시 대입이 없어서 새 값을 임시 변수에 먼저 구해 두고 옮겨요.
C++는 std::tie(skip, c1, c2, c3) = std::make_tuple(...)로 한꺼번에 바꿀 수도 있지만, 임시 변수가 더 흔해요.
둘째 함정은 아직 닿을 수 없는 상태의 처음 값이에요.
첫 노트 앞에서 c1·c2·c3를 0으로 두면 첫 노트부터 2배·3배를 받은 셈이 돼요.
Python float("-inf"), JS·TS -Infinity처럼 아주 작은 값에서 시작해요.
Java·C#·C·C++의 정수에는 무한대가 없고 Integer.MIN_VALUE(int.MinValue, INT_MIN)에 음수 점수를 더하면 넘쳐서 Java·C#에서는 큰 양수가 되고 C·C++에서는 정의되지 않은 동작이니, 그 절반처럼 여유 있는 값을 써요.
크레이콘에는 이런 상수가 없어서 -1조 같은 수를 직접 둬요.
셋째로, 마지막 노트를 보내는 경우와 하나도 치지 않는 경우(0점)까지 네 상태 모두에서 가장 큰 값을 답으로 골라요.
n = int(input())a = list(map(int, input().split())) # 노트 하나를 지날 때마다 상태 넷의 가장 좋은 점수를 이어 간다# skip: 이 노트를 보냈다(콤보 없음)# c1, c2: 이 노트가 콤보의 첫째·둘째# c3: 이 노트가 콤보의 셋째 이후(3배)NONE = float("-inf") # 아직 닿을 수 없는 상태skip, c1, c2, c3 = 0, NONE, NONE, NONEfor x in a: skip, c1, c2, c3 = max(skip, c1, c2, c3), skip + x, c1 + 2 * x, max(c2, c3) + 3 * xprint(max(skip, c1, c2, c3))const nums = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = nums[0];// skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배). -Infinity는 아직 닿을 수 없는 상태let skip = 0, c1 = -Infinity, c2 = -Infinity, c3 = -Infinity;for (let i = 1; i <= n; i++) { const x = nums[i]; [skip, c1, c2, c3] = [Math.max(skip, c1, c2, c3), skip + x, c1 + 2 * x, Math.max(c2, c3) + 3 * x];}console.log(Math.max(skip, c1, c2, c3));import { readFileSync } from "node:fs";const nums: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n: number = nums[0];// skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배). -Infinity는 아직 닿을 수 없는 상태let skip = 0, c1 = -Infinity, c2 = -Infinity, c3 = -Infinity;for (let i = 1; i <= n; i++) { const x: number = nums[i]; [skip, c1, c2, c3] = [Math.max(skip, c1, c2, c3), skip + x, c1 + 2 * x, Math.max(c2, c3) + 3 * x];}console.log(Math.max(skip, c1, c2, c3));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { // 아직 닿을 수 없는 상태: 어떤 점수보다도 훨씬 작고, 3배 점수를 더해도 넘치지 않는 값 static final int NONE = Integer.MIN_VALUE / 2; public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); StringTokenizer st = new StringTokenizer(in.readLine()); // skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배) int skip = 0, c1 = NONE, c2 = NONE, c3 = NONE; for (int i = 0; i < n; i++) { int x = Integer.parseInt(st.nextToken()); int nSkip = Math.max(Math.max(skip, c1), Math.max(c2, c3)); int n1 = skip + x; int n2 = c1 + 2 * x; int n3 = Math.max(c2, c3) + 3 * x; skip = nSkip; c1 = n1; c2 = n2; c3 = n3; } System.out.println(Math.max(Math.max(skip, c1), Math.max(c2, c3))); }}using System;using System.Linq; class Program{ // 아직 닿을 수 없는 상태: 어떤 점수보다도 훨씬 작고, 3배 점수를 더해도 넘치지 않는 값 const int None = int.MinValue / 2; static void Main() { int n = int.Parse(Console.ReadLine()); int[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); // skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배) int skip = 0, c1 = None, c2 = None, c3 = None; foreach (int x in a) { (skip, c1, c2, c3) = (Math.Max(Math.Max(skip, c1), Math.Max(c2, c3)), skip + x, c1 + 2 * x, Math.Max(c2, c3) + 3 * x); } Console.WriteLine(Math.Max(Math.Max(skip, c1), Math.Max(c2, c3))); }}#include <algorithm>#include <climits>#include <iostream> int main() { // 아직 닿을 수 없는 상태: 어떤 점수보다도 훨씬 작고, 3배 점수를 더해도 넘치지 않는 값 const int NONE = INT_MIN / 2; int n; std::cin >> n; // skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배) int skip = 0, c1 = NONE, c2 = NONE, c3 = NONE; for (int i = 0; i < n; i++) { int x; std::cin >> x; int ns = std::max({skip, c1, c2, c3}); int n1 = skip + x, n2 = c1 + 2 * x, n3 = std::max(c2, c3) + 3 * x; skip = ns; c1 = n1; c2 = n2; c3 = n3; } std::cout << std::max({skip, c1, c2, c3}) << '\n';}#include <limits.h>#include <stdio.h> /* 아직 닿을 수 없는 상태: 어떤 점수보다도 훨씬 작고, 3배 점수를 더해도 넘치지 않는 값 */#define NONE (INT_MIN / 2) static int max2(int a, int b) { return a > b ? a : b; } int main(void) { int n; scanf("%d", &n); /* skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배) */ int skip = 0, c1 = NONE, c2 = NONE, c3 = NONE; for (int i = 0; i < n; i++) { int x; scanf("%d", &x); int ns = max2(max2(skip, c1), max2(c2, c3)); int n1 = skip + x, n2 = c1 + 2 * x, n3 = max2(c2, c3) + 3 * x; skip = ns; c1 = n1; c2 = n2; c3 = n3; } printf("%d\n", max2(max2(skip, c1), max2(c2, c3))); return 0;}n = 콘솔.줄읽기().수로변환();a = 콘솔.수들읽기();// 아직 닿을 수 없는 상태: 어떤 점수보다도 훨씬 작은 값못감 = -1000000000000;// skip: 이 노트를 보냄, c1·c2: 콤보 첫째·둘째, c3: 셋째 이후(3배)skip = 0;c1 = 못감;c2 = 못감;c3 = 못감;각각 (x 에서 a){ // 새 값은 모두 이전 값으로 계산한다: 먼저 따로 구해 두고 한꺼번에 바꾼다 새skip = 수학.큰수(수학.큰수(skip, c1), 수학.큰수(c2, c3)); 새c1 = skip + x; 새c2 = c1 + 2 * x; 새c3 = 수학.큰수(c2, c3) + 3 * x; skip = 새skip; c1 = 새c1; c2 = 새c2; c3 = 새c3;}콘솔.쓰기(수학.큰수(수학.큰수(skip, c1), 수학.큰수(c2, c3)));