정수 n개가 한 줄로 놓인 목록 a_1, a_2, …, a_n과 명령 q개가 주어진다.
명령 하나는 "방향 연산 처음값" 꼴이다.
연산은 두 정수 x, y로 값 하나를 만드는 함수이며 다섯 가지가 있다.
add는 x + y, sub는 x - y, max는 둘 가운데 큰 값, min은 둘 가운데 작은 값, gap은 x - y의 절댓값이다.
방향이 L이면 왼쪽 접기를 한다. 값 v를 처음값으로 두고, a_1부터 a_n까지 차례로 v를 연산(v, a_i)로 바꾼다.
방향이 R이면 오른쪽 접기를 한다. 값 v를 처음값으로 두고, a_n부터 a_1까지 거꾸로 v를 연산(a_i, v)로 바꾼다.
오른쪽 접기에서는 목록의 원소가 연산의 첫째 자리에, 지금까지의 값이 둘째 자리에 들어간다.
명령마다 접기가 끝났을 때의 v를 구하라.
목록과 연산 함수와 처음값을 받는 접기 함수를 방향마다 하나씩 만들고, 연산 이름에 맞는 함수를 골라 넘겨서 풀어 보자.
예제의 목록은 5 2 4이다.
"L sub 20"은 ((20 - 5) - 2) - 4 = 9이고, "R sub 20"은 5 - (2 - (4 - 20)) = -13이다.
"L gap 0"은 v가 5, 3, 1로 바뀌어 1이고, "R gap 0"은 v가 4, 2, 3으로 바뀌어 3이다.
입력
첫 줄에 n과 q가 빈칸으로 나뉘어 주어진다. 둘째 줄에 a_1부터 a_n까지 빈칸 하나로 나뉘어 주어진다. 다음 q줄에 명령이 한 줄에 하나씩, 방향(L 또는 R)과 연산 이름(add, sub, max, min, gap 가운데 하나)과 처음값이 빈칸 하나로 나뉘어 주어진다. 1 ≤ n ≤ 1,000, 1 ≤ q ≤ 200, -1,000,000,000 ≤ a_i ≤ 1,000,000,000, -1,000,000,000 ≤ 처음값 ≤ 1,000,000,000
출력
명령마다 주어진 차례대로 답을 한 줄에 하나씩 출력한다. 수는 쉼표 없이 숫자만 쓴다
예시 1 · stdin
3 5
5 2 4
L sub 20
R sub 20
L gap 0
R gap 0
L max -7
stdout
9
-13
1
3
5
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
함수를 값으로 다루는 법이 언어마다 달라요. 여기서는 함수를 '이름 → 함수' 표에 넣고, 접기 함수에 인수로 넘겨요. Python은 함수 이름이 곧 값이라 {"add": operator.add, "max": max}처럼 내장 함수도 그대로 넣어요. JS·TS는 화살표 함수 (p, q) => p - q를 써요. Java는 LongBinaryOperator에 람다나 Long::sum·Math::max 같은 메서드 참조를 담고 f.applyAsLong(p, q)로 불러요. C#은 Func<long, long, long>에 람다나 Math.Max를 담아요. C는 함수 포인터 long long (*f)(long long, long long)를 쓰고, C++은 람다를 std::function에 담아요. 크레이콘에는 람다가 없어서 이름 있는 함수를 만들고, 괄호 없이 이름만 써서 ops["sub"] = 덜기;처럼 넣은 뒤 f(acc, x)로 불러요. 함정 하나: 오른쪽 접기는 훑는 방향만 바뀌는 것이 아니라 인수 자리도 바뀌어요. 오른쪽부터 훑으면서 f(v, a_i)로 부르면 예제의 R sub 20이 ((20 - 4) - 2) - 5 = 9가 돼요(답은 -13). JS의 reduceRight도 f(지금까지의 값, 원소) 차례로 부르므로 그대로 쓰면 이렇게 틀려요. 거꾸로 인수 자리만 바꾸고 왼쪽부터 훑어도 틀리고, L과 R을 가리지 않아도 틀려요. 함정 둘: JS에서 list.reduce(Math.max, init)처럼 내장 함수를 그대로 넘기면 안 돼요. reduce는 함수에 (지금까지의 값, 원소, 번호, 배열) 네 개를 넘기고 Math.max는 받은 것을 모두 수로 바꿔 견주므로 NaN이 나와요(예제의 L max -7). 두 개만 받는 화살표 함수로 감싸요. 함정 셋: 처음값을 빼먹으면 안 돼요. Python functools.reduce(f, items)는 처음값을 주지 않으면 첫 원소에서 시작해서, 예제의 L sub 20이 9가 아니라 (5 - 2) - 4 = -1이 돼요. 함정 넷: 10억짜리 수 1,000개를 더하면 1조라서 32비트를 넘어요. Java·C#은 long, C·C++은 long long으로 접어요. C++에서 지금까지의 값을 int에 담으면 오류 없이 엉뚱한 수가 돼요. Python 정수는 한계가 없고 JS·TS·크레이콘의 수는 2^53까지 정확해요.
Pythonmain.py · 33 줄
import sysfrom operator import add, subdef gap(p, q): return abs(p - q)# 이름 → 함수. 함수도 값이라서 사전에 넣을 수 있다 (max, min은 내장 함수 그대로)OPS = {"add": add, "sub": sub, "max": max, "min": min, "gap": gap}def fold_left(items, f, init): acc = init for x in items: acc = f(acc, x) # 지금까지의 값이 왼쪽 return accdef fold_right(items, f, init): acc = init for x in reversed(items): acc = f(x, acc) # 지금까지의 값이 오른쪽 return accdef main(): lines = sys.stdin.read().split("\n") n, q = map(int, lines[0].split()) items = [int(v) for v in lines[1].split()] out = [] for line in lines[2:2 + q]: side, name, init = line.split() fold = fold_left if side == "L" else fold_right out.append(fold(items, OPS[name], int(init))) print("\n".join(map(str, out)))main()
JavaScriptmain.js · 32 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);const items = lines[1].trim().split(/\s+/).map(Number);// 이름 → 함수. 인수를 꼭 두 개만 받도록 화살표 함수로 감싼다const OPS = { add: (p, q) => p + q, sub: (p, q) => p - q, max: (p, q) => Math.max(p, q), min: (p, q) => Math.min(p, q), gap: (p, q) => Math.abs(p - q),};function foldLeft(list, f, init) { let acc = init; for (const x of list) acc = f(acc, x); // 지금까지의 값이 왼쪽 return acc;}function foldRight(list, f, init) { let acc = init; for (let i = list.length - 1; i >= 0; i--) acc = f(list[i], acc); // 지금까지의 값이 오른쪽 return acc;}const out = [];for (let k = 0; k < q; k++) { const [side, name, init] = lines[2 + k].trim().split(/\s+/); const fold = side === "L" ? foldLeft : foldRight; out.push(fold(items, OPS[name], Number(init)));}console.log(out.join("\n"));
TypeScriptmain.ts · 37 줄
import { readFileSync } from "node:fs";type Op = (p: number, q: number) => number;type Fold = (list: number[], f: Op, init: number) => number;const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);const items: number[] = lines[1].trim().split(/\s+/).map(Number);// 이름 → 함수. 인수를 꼭 두 개만 받도록 화살표 함수로 감싼다const OPS: Record<string, Op> = { add: (p, q) => p + q, sub: (p, q) => p - q, max: (p, q) => Math.max(p, q), min: (p, q) => Math.min(p, q), gap: (p, q) => Math.abs(p - q),};const foldLeft: Fold = (list, f, init) => { let acc = init; for (const x of list) acc = f(acc, x); // 지금까지의 값이 왼쪽 return acc;};const foldRight: Fold = (list, f, init) => { let acc = init; for (let i = list.length - 1; i >= 0; i--) acc = f(list[i], acc); // 지금까지의 값이 오른쪽 return acc;};const out: number[] = [];for (let k = 0; k < q; k++) { const [side, name, init] = lines[2 + k].trim().split(/\s+/); const fold: Fold = side === "L" ? foldLeft : foldRight; out.push(fold(items, OPS[name], Number(init)));}console.log(out.join("\n"));
JavaMain.java · 48 줄
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.HashMap;import java.util.Map;import java.util.StringTokenizer;import java.util.function.LongBinaryOperator;public class Main { static long foldLeft(long[] items, LongBinaryOperator f, long init) { long acc = init; for (long x : items) acc = f.applyAsLong(acc, x); // 지금까지의 값이 왼쪽 return acc; } static long foldRight(long[] items, LongBinaryOperator f, long init) { long acc = init; for (int i = items.length - 1; i >= 0; i--) acc = f.applyAsLong(items[i], acc); // 지금까지의 값이 오른쪽 return acc; } public static void main(String[] args) throws Exception { // 이름 → 함수. 이미 있는 메서드는 Long::sum처럼, 없는 것은 람다로 적는다 Map<String, LongBinaryOperator> ops = new HashMap<>(); ops.put("add", Long::sum); ops.put("sub", (p, q) -> p - q); ops.put("max", Math::max); ops.put("min", Math::min); ops.put("gap", (p, q) -> Math.abs(p - q)); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); long[] items = new long[n]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) items[i] = Long.parseLong(st.nextToken()); StringBuilder out = new StringBuilder(); for (int k = 0; k < q; k++) { st = new StringTokenizer(br.readLine()); String side = st.nextToken(); LongBinaryOperator f = ops.get(st.nextToken()); long init = Long.parseLong(st.nextToken()); out.append(side.equals("L") ? foldLeft(items, f, init) : foldRight(items, f, init)).append('\n'); } System.out.print(out); }}
C#Main.cs · 47 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static long FoldLeft(long[] items, Func<long, long, long> f, long init) { long acc = init; foreach (long x in items) acc = f(acc, x); // 지금까지의 값이 왼쪽 return acc; } static long FoldRight(long[] items, Func<long, long, long> f, long init) { long acc = init; for (int i = items.Length - 1; i >= 0; i--) acc = f(items[i], acc); // 지금까지의 값이 오른쪽 return acc; } static void Main() { // 이름 → 함수. Math.Max는 형이 여러 가지라 Func<long, long, long>에 넣으면 long용이 골라진다 var ops = new Dictionary<string, Func<long, long, long>> { ["add"] = (p, q) => p + q, ["sub"] = (p, q) => p - q, ["max"] = Math.Max, ["min"] = Math.Min, ["gap"] = (p, q) => Math.Abs(p - q), }; string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int q2 = int.Parse(first[1]); long[] items = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); var sb = new StringBuilder(); for (int k = 0; k < q2; k++) { string[] parts = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); Func<long, long, long> f = ops[parts[1]]; long init = long.Parse(parts[2]); sb.Append(parts[0] == "L" ? FoldLeft(items, f, init) : FoldRight(items, f, init)).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 47 줄
#include <algorithm>#include <cstdlib>#include <functional>#include <iostream>#include <map>#include <string>#include <vector>using Op = std::function<long long(long long, long long)>;long long foldLeft(const std::vector<long long> &items, const Op &f, long long init) { long long acc = init; for (long long x : items) acc = f(acc, x); // 지금까지의 값이 왼쪽 return acc;}long long foldRight(const std::vector<long long> &items, const Op &f, long long init) { long long acc = init; for (auto it = items.rbegin(); it != items.rend(); ++it) acc = f(*it, acc); // 지금까지의 값이 오른쪽 return acc;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); // 이름 → 함수. 람다를 std::function에 담는다 const std::map<std::string, Op> ops = { {"add", [](long long p, long long q) { return p + q; }}, {"sub", [](long long p, long long q) { return p - q; }}, {"max", [](long long p, long long q) { return std::max(p, q); }}, {"min", [](long long p, long long q) { return std::min(p, q); }}, {"gap", [](long long p, long long q) { return std::llabs(p - q); }}, }; int n, q; std::cin >> n >> q; std::vector<long long> items(n); for (auto &x : items) std::cin >> x; for (int k = 0; k < q; k++) { std::string side, name; long long init; std::cin >> side >> name >> init; const Op &f = ops.at(name); std::cout << (side == "L" ? foldLeft(items, f, init) : foldRight(items, f, init)) << '\n'; }}
Cmain.c · 46 줄
#include <stdio.h>#include <string.h>/* 함수를 가리키는 포인터의 형: long long 둘을 받아 long long을 돌려주는 함수 */typedef long long (*Op)(long long, long long);long long op_add(long long p, long long q) { return p + q; }long long op_sub(long long p, long long q) { return p - q; }long long op_max(long long p, long long q) { return p > q ? p : q; }long long op_min(long long p, long long q) { return p < q ? p : q; }long long op_gap(long long p, long long q) { return p > q ? p - q : q - p; }/* 이름 → 함수 표 */struct { const char *name; Op f; } OPS[] = { {"add", op_add}, {"sub", op_sub}, {"max", op_max}, {"min", op_min}, {"gap", op_gap},};long long fold_left(const long long *items, int n, Op f, long long init) { long long acc = init; for (int i = 0; i < n; i++) acc = f(acc, items[i]); /* 지금까지의 값이 왼쪽 */ return acc;}long long fold_right(const long long *items, int n, Op f, long long init) { long long acc = init; for (int i = n - 1; i >= 0; i--) acc = f(items[i], acc); /* 지금까지의 값이 오른쪽 */ return acc;}long long items[1000];int main(void) { int n, q; scanf("%d %d", &n, &q); for (int i = 0; i < n; i++) scanf("%lld", &items[i]); for (int k = 0; k < q; k++) { char side[4], name[8]; long long init; scanf("%3s %7s %lld", side, name, &init); Op f = NULL; for (int j = 0; j < 5; j++) if (strcmp(OPS[j].name, name) == 0) f = OPS[j].f; printf("%lld\n", side[0] == 'L' ? fold_left(items, n, f, init) : fold_right(items, n, f, init)); } return 0;}
Craykonmain.cray · 70 줄
더하기(p, q){ 돌려주기 p + q;}덜기(p, q){ 돌려주기 p - q;}큰쪽(p, q){ 돌려주기 수학.큰수(p, q);}작은쪽(p, q){ 돌려주기 수학.작은수(p, q);}차이(p, q){ 돌려주기 수학.절댓값(p - q);}// 이름 → 함수. 함수 이름을 괄호 없이 쓰면 함수 자체가 값이 된다ops = 사전();ops["add"] = 더하기;ops["sub"] = 덜기;ops["max"] = 큰쪽;ops["min"] = 작은쪽;ops["gap"] = 차이;왼쪽접기(items, f, init){ acc = init; 각각 (x 에서 items) { acc = f(acc, x); // 지금까지의 값이 왼쪽 } 돌려주기 acc;}오른쪽접기(items, f, init){ acc = init; 반복 (i = items.개수 - 1; i >= 0; i--) { acc = f(items[i], acc); // 지금까지의 값이 오른쪽 } 돌려주기 acc;}첫줄 = 콘솔.수들읽기();q = 첫줄[1];items = 콘솔.수들읽기();반복 (k = 0; k < q; k++){ parts = 콘솔.줄읽기().나누기(" "); f = ops[parts[1]]; init = parts[2].수로변환(); 만약 (parts[0] == "L") { 콘솔.쓰기(왼쪽접기(items, f, init)); } 아니면 { 콘솔.쓰기(오른쪽접기(items, f, init)); }}