어떤 물건의 n일 동안의 값 p_1, p_2, …, p_n이 날짜 차례로 주어진다.
매매 로봇은 이 물건을 한 번에 한 개만 들고 있을 수 있고, 처음에는 들고 있지 않다.
로봇은 날마다 그날의 값 p를 보고 아래 규칙에서 꼭 한 가지만 따른다.
물건을 들고 있는 날에는 산 값을 c, 산 날부터 어제까지의 값 가운데 가장 높은 값을 h라고 할 때 다음 셋 가운데 하나를 한다.
규칙 1: p가 c + g 이상이면 p에 판다.
규칙 2: 규칙 1에 맞지 않고 p가 h - w 이하이면 p에 판다. 이때 p가 c보다 작으면 손해를 본 것이므로 다음 날부터 k일 동안 쉰다.
규칙 3: 둘 다 아니면 팔지 않고, p가 h보다 크면 h를 p로 올린다.
물건을 들고 있지 않은 날에는 다음 둘 가운데 하나를 한다.
규칙 4: 쉬는 날이 남아 있으면 값이 얼마든 아무것도 하지 않고, 남은 쉬는 날이 하루 줄어든다.
규칙 5: 쉬는 날이 남아 있지 않고 p가 B 이하이면 p에 산다. 이때 c와 h는 모두 p가 된다. p가 B보다 크면 아무것도 하지 않는다.
판 날에는 값이 B 이하여도 다시 사지 않는다.
판 날은 물건을 들고 시작한 날이기 때문이다.
로봇이 사고판 기록을 날짜 차례로 구하고, 판 값에서 산 값을 뺀 것을 판 때마다 모두 더한 이익과 마지막 날이 지난 뒤에 물건을 들고 있는지를 구하라.
예제에서 B = 50, g = 20, w = 10, k = 2이다.
2일에 48에 사고, 3일에 h가 55가 되고, 4일의 44는 55 - 10 이하라서 팔며 손해라서 5일과 6일을 쉰다.
7일에 50에 사서 8일에 70에 판다.
9일에 30에 사고, 10일에 h가 42가 되고, 11일의 32는 42 - 10 이하라서 판다.
이번에는 손해가 아니라서 쉬지 않지만 판 날이라 11일에는 사지 않고, 12일에 31에 산다.
이익은 -4 + 20 + 2 = 18이다.
입력
첫째 줄에 n, B, g, w, k가 빈칸으로 나뉘어 주어진다. 둘째 줄에 p_1부터 p_n까지가 빈칸 하나로 나뉘어 주어진다. 모두 정수이다. 1 ≤ n ≤ 10,000, 1 ≤ B ≤ 100,000, 1 ≤ g ≤ 100,000, 1 ≤ w ≤ 100,000, 0 ≤ k ≤ 100, 1 ≤ p_i ≤ 100,000
출력
로봇이 사거나 판 날마다 날짜 차례로 한 줄씩 출력한다. 산 날은 "buy 날짜 값", 판 날은 "sell 날짜 값"으로 쓰고, 날짜는 1부터 센다. 마지막 줄에 이익과, 마지막 날이 지난 뒤에 물건을 들고 있으면 1, 아니면 0을 빈칸 하나로 띄워 출력한다. 수는 쉼표 없이 숫자만 쓴다
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
규칙이 '들고 있는 날 / 들고 있지 않은 날'로 먼저 갈리고 그 안에서 다시 갈리므로, 바깥 if … else 안에 if … else if … else를 넣은 모양 그대로 써요. 어느 언어든 뼈대는 같고 낱말만 달라요. Python은 elif와 들여쓰기로, JS·TS·C·C++·Java·C#은 else if와 중괄호로, 크레이콘은 만약 … 아니면 만약 … 아니면으로 써요. 함정 하나: 바깥 갈림을 else 없이 if (들고 있다) { … }와 if (들고 있지 않다) { … } 둘로 나눠 쓰면 안 돼요. 첫 if에서 팔고 나면 둘째 조건이 참이 되어 같은 날 규칙 4나 5까지 해 버려요. 예제 11일에 32에 팔고 곧바로 32에 다시 사고, 4일에는 판 날이 쉬는 날로 세어져 6일에 45에 사요. else는 '위 조건이 거짓일 때'가 아니라 '위 갈래로 가지 않았을 때'예요. 함정 둘: 손해인지 가리는 안쪽 if는 규칙 2 안에만 있어요. 이것을 빼고 규칙 2로 팔 때마다 쉬면 예제 11일 뒤에 이틀을 쉬어서 12일에 사지 못해요. 산 값과 꼭 같은 값에 판 것은 손해가 아니에요(<이지 <=가 아니에요). 함정 셋: 쉬는 날은 판 다음 날부터 세요. 판 날을 쉬는 날에 넣으면 하루 모자라서 예제 6일에 45에 사요. 함정 넷: h는 규칙 3에서만 올라가고 살 때마다 산 값으로 돌아가요. 올리는 것을 빼먹으면 예제 4일에 팔지 않고, 살 때 되돌리지 않으면 지난 거래의 고점 55가 남아서 10일의 42에 팔아요. 함정 다섯: 경계는 모두 '이상·이하'예요. 예제 7일의 50(= B), 8일의 70(= c + g), 11일의 32(= h - w)가 모두 경계에 꼭 걸려요. 이익은 가장 클 때도 5억쯤이라 32비트 정수에 들어가요.
Pythonmain.py · 39 줄
import sysdef main(): data = sys.stdin.read().split() n, B, g, w, k = (int(v) for v in data[:5]) prices = [int(v) for v in data[5:5 + n]] holding = False cost = 0 # 산 값 high = 0 # 산 날부터 지금까지 가장 높았던 값 rest = 0 # 남은 쉬는 날 수 profit = 0 out = [] for day, p in enumerate(prices, start=1): if holding: if p >= cost + g: # 규칙 1: 이익 실현 out.append(f"sell {day} {p}") profit += p - cost holding = False elif p <= high - w: # 규칙 2: 고점에서 w 이상 내려옴 out.append(f"sell {day} {p}") profit += p - cost holding = False if p < cost: # 손해를 보고 팔았을 때만 쉰다 rest = k else: # 규칙 3: 그대로 들고 간다 high = max(high, p) else: # 판 날에는 이쪽으로 오지 않는다 if rest > 0: # 규칙 4: 쉬는 날 rest -= 1 elif p <= B: # 규칙 5: 산다 out.append(f"buy {day} {p}") holding = True cost = p high = p out.append(f"{profit} {1 if holding else 0}") print("\n".join(out))main()
JavaScriptmain.js · 42 줄
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const [n, B, g, w, k] = data;let holding = false;let cost = 0; // 산 값let high = 0; // 산 날부터 지금까지 가장 높았던 값let rest = 0; // 남은 쉬는 날 수let profit = 0;const out = [];for (let day = 1; day <= n; day++) { const p = data[4 + day]; if (holding) { if (p >= cost + g) { // 규칙 1: 이익 실현 out.push(`sell ${day} ${p}`); profit += p - cost; holding = false; } else if (p <= high - w) { // 규칙 2: 고점에서 w 이상 내려옴 out.push(`sell ${day} ${p}`); profit += p - cost; holding = false; if (p < cost) rest = k; // 손해를 보고 팔았을 때만 쉰다 } else { // 규칙 3: 그대로 들고 간다 high = Math.max(high, p); } } else { // 판 날에는 이쪽으로 오지 않는다 if (rest > 0) { rest--; // 규칙 4: 쉬는 날 } else if (p <= B) { // 규칙 5: 산다 out.push(`buy ${day} ${p}`); holding = true; cost = p; high = p; } }}out.push(`${profit} ${holding ? 1 : 0}`);console.log(out.join("\n"));
TypeScriptmain.ts · 43 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const [n, B, g, w, k] = data;let holding = false;let cost = 0; // 산 값let high = 0; // 산 날부터 지금까지 가장 높았던 값let rest = 0; // 남은 쉬는 날 수let profit = 0;const out: string[] = [];for (let day = 1; day <= n; day++) { const p = data[4 + day]; if (holding) { if (p >= cost + g) { // 규칙 1: 이익 실현 out.push(`sell ${day} ${p}`); profit += p - cost; holding = false; } else if (p <= high - w) { // 규칙 2: 고점에서 w 이상 내려옴 out.push(`sell ${day} ${p}`); profit += p - cost; holding = false; if (p < cost) rest = k; // 손해를 보고 팔았을 때만 쉰다 } else { // 규칙 3: 그대로 들고 간다 high = Math.max(high, p); } } else { // 판 날에는 이쪽으로 오지 않는다 if (rest > 0) { rest--; // 규칙 4: 쉬는 날 } else if (p <= B) { // 규칙 5: 산다 out.push(`buy ${day} ${p}`); holding = true; cost = p; high = p; } }}out.push(`${profit} ${holding ? 1 : 0}`);console.log(out.join("\n"));
JavaMain.java · 51 줄
import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.StreamTokenizer;public class Main { public static void main(String[] args) throws Exception { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); int[] head = new int[5]; for (int i = 0; i < 5; i++) { in.nextToken(); head[i] = (int) in.nval; } int n = head[0], B = head[1], g = head[2], w = head[3], k = head[4]; boolean holding = false; int cost = 0; // 산 값 int high = 0; // 산 날부터 지금까지 가장 높았던 값 int rest = 0; // 남은 쉬는 날 수 int profit = 0; StringBuilder out = new StringBuilder(); for (int day = 1; day <= n; day++) { in.nextToken(); int p = (int) in.nval; if (holding) { if (p >= cost + g) { // 규칙 1: 이익 실현 out.append("sell ").append(day).append(' ').append(p).append('\n'); profit += p - cost; holding = false; } else if (p <= high - w) { // 규칙 2: 고점에서 w 이상 내려옴 out.append("sell ").append(day).append(' ').append(p).append('\n'); profit += p - cost; holding = false; if (p < cost) rest = k; // 손해를 보고 팔았을 때만 쉰다 } else { // 규칙 3: 그대로 들고 간다 high = Math.max(high, p); } } else { // 판 날에는 이쪽으로 오지 않는다 if (rest > 0) { // 규칙 4: 쉬는 날 rest--; } else if (p <= B) { // 규칙 5: 산다 out.append("buy ").append(day).append(' ').append(p).append('\n'); holding = true; cost = p; high = p; } } } out.append(profit).append(' ').append(holding ? 1 : 0).append('\n'); System.out.print(out); }}
C#Main.cs · 58 줄
using System;using System.Text;class Program{ static void Main() { string[] data = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), B = int.Parse(data[1]), g = int.Parse(data[2]), w = int.Parse(data[3]), k = int.Parse(data[4]); bool holding = false; int cost = 0; // 산 값 int high = 0; // 산 날부터 지금까지 가장 높았던 값 int rest = 0; // 남은 쉬는 날 수 int profit = 0; var sb = new StringBuilder(); for (int day = 1; day <= n; day++) { int p = int.Parse(data[4 + day]); if (holding) { if (p >= cost + g) // 규칙 1: 이익 실현 { sb.Append("sell ").Append(day).Append(' ').Append(p).Append('\n'); profit += p - cost; holding = false; } else if (p <= high - w) // 규칙 2: 고점에서 w 이상 내려옴 { sb.Append("sell ").Append(day).Append(' ').Append(p).Append('\n'); profit += p - cost; holding = false; if (p < cost) rest = k; // 손해를 보고 팔았을 때만 쉰다 } else // 규칙 3: 그대로 들고 간다 { high = Math.Max(high, p); } } else // 판 날에는 이쪽으로 오지 않는다 { if (rest > 0) // 규칙 4: 쉬는 날 { rest--; } else if (p <= B) // 규칙 5: 산다 { sb.Append("buy ").Append(day).Append(' ').Append(p).Append('\n'); holding = true; cost = p; high = p; } } } sb.Append(profit).Append(' ').Append(holding ? 1 : 0).Append('\n'); Console.Write(sb); }}
C++main.cpp · 43 줄
#include <algorithm>#include <iostream>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, B, g, w, k; std::cin >> n >> B >> g >> w >> k; bool holding = false; int cost = 0; // 산 값 int high = 0; // 산 날부터 지금까지 가장 높았던 값 int rest = 0; // 남은 쉬는 날 수 int profit = 0; for (int day = 1; day <= n; day++) { int p; std::cin >> p; if (holding) { if (p >= cost + g) { // 규칙 1: 이익 실현 std::cout << "sell " << day << ' ' << p << '\n'; profit += p - cost; holding = false; } else if (p <= high - w) { // 규칙 2: 고점에서 w 이상 내려옴 std::cout << "sell " << day << ' ' << p << '\n'; profit += p - cost; holding = false; if (p < cost) rest = k; // 손해를 보고 팔았을 때만 쉰다 } else { // 규칙 3: 그대로 들고 간다 high = std::max(high, p); } } else { // 판 날에는 이쪽으로 오지 않는다 if (rest > 0) { // 규칙 4: 쉬는 날 rest--; } else if (p <= B) { // 규칙 5: 산다 std::cout << "buy " << day << ' ' << p << '\n'; holding = true; cost = p; high = p; } } } std::cout << profit << ' ' << (holding ? 1 : 0) << '\n';}
Cmain.c · 41 줄
#include <stdio.h>int main(void) { int n, B, g, w, k; scanf("%d %d %d %d %d", &n, &B, &g, &w, &k); int holding = 0; int cost = 0; /* 산 값 */ int high = 0; /* 산 날부터 지금까지 가장 높았던 값 */ int rest = 0; /* 남은 쉬는 날 수 */ int profit = 0; for (int day = 1; day <= n; day++) { int p; scanf("%d", &p); if (holding) { if (p >= cost + g) { /* 규칙 1: 이익 실현 */ printf("sell %d %d\n", day, p); profit += p - cost; holding = 0; } else if (p <= high - w) { /* 규칙 2: 고점에서 w 이상 내려옴 */ printf("sell %d %d\n", day, p); profit += p - cost; holding = 0; if (p < cost) rest = k; /* 손해를 보고 팔았을 때만 쉰다 */ } else { /* 규칙 3: 그대로 들고 간다 */ if (p > high) high = p; } } else { /* 판 날에는 이쪽으로 오지 않는다 */ if (rest > 0) { /* 규칙 4: 쉬는 날 */ rest--; } else if (p <= B) { /* 규칙 5: 산다 */ printf("buy %d %d\n", day, p); holding = 1; cost = p; high = p; } } } printf("%d %d\n", profit, holding); return 0;}
Craykonmain.cray · 62 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];B = 첫줄[1];g = 첫줄[2];w = 첫줄[3];k = 첫줄[4];prices = 콘솔.수들읽기();holding = 거짓;cost = 0; // 산 값high = 0; // 산 날부터 지금까지 가장 높았던 값rest = 0; // 남은 쉬는 날 수profit = 0;반복 (day = 1; day <= n; day++){ p = prices[day - 1]; 만약 (holding) { 만약 (p >= cost + g) { 콘솔.쓰기("sell " + day + " " + p); profit = profit + p - cost; holding = 거짓; } 아니면 만약 (p <= high - w) { 콘솔.쓰기("sell " + day + " " + p); profit = profit + p - cost; holding = 거짓; 만약 (p < cost) { rest = k; } } 아니면 { high = 수학.큰수(high, p); } } 아니면 { 만약 (rest > 0) { rest = rest - 1; } 아니면 만약 (p <= B) { 콘솔.쓰기("buy " + day + " " + p); holding = 참; cost = p; high = p; } }}만약 (holding){ 콘솔.쓰기(profit + " 1");}아니면{ 콘솔.쓰기(profit + " 0");}