정수 n개로 된 수열 a₁ … aₙ이 주어진다.
이 수열에서 몇 개를 골라(원래 차례는 그대로 두고, 사이를 건너뛰어도 된다) 만든 수열이 엄격하게 증가할 때(뒤의 수가 앞의 수보다 항상 크다, 같으면 안 된다), 그런 수열의 가장 긴 길이를 출력하라.
하나만 고른 수열도 증가하는 수열로 친다.
예를 들어 3 1 4 1 5 9 2 6에서는 1 4 5 9(또는 3 4 5 6 등)를 골라 길이 4가 가장 길다.
첫 줄에 n, 둘째 줄에 a₁ … aₙ이 빈칸으로 나뉘어 주어진다.
8 3 1 4 1 5 9 2 6
4
5 2 2 2 2 2
1
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
length[i] = 'a[i]로 끝나는 가장 긴 증가 수열의 길이'로 두면, 앞의 j < i 가운데 a[j] < a[i]인 것의 length[j] + 1 중 가장 큰 값이에요(없으면 1).
두 겹 반복이 n²/2 = 약 200만 번이라 8개 언어 모두 넉넉해요(크레이콘 실행 걸음 한도 약 5천만 안).
함정 셋: 같은 값도 이어 붙이는 <=는 '엄격히 증가'가 아니에요.
답은 마지막 칸 length[n-1]이 아니라 모든 칸 중 가장 큰 값이에요 — 가장 긴 수열이 끝에서 끝나지 않을 수 있어요.
그리고 붙어 있는 구간만 세면 사이를 건너뛰는 수열을 놓쳐요.
가장 큰 값 구하기가 언어마다 달라요: Python max(length), C# LINQ length.Max(), C++ *std::max_element(…), JavaScript·TypeScript Math.max(...length)(펼친 인자 개수에 한계가 있어서 수십만 칸이 넘으면 반복문이 안전해요).
Java와 C는 best를 따로 들고 가요(Java는 Arrays.stream(length).max().getAsInt()도 돼요).
처음 값 채우기도 달라요: Python [1] * n, JS new Array(n).fill(1), C++ vector<int>(n, 1), Java·C#·C는 0으로 채워지니 length[i] = 1을 직접 써요.
크레이콘은 새목록(n, 1)로 만들고 best를 따로 들고 가요.
import sys data = sys.stdin.read().split()n = int(data[0])a = list(map(int, data[1:1 + n])) # length[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이length = [1] * nfor i in range(n): for j in range(i): if a[j] < a[i] and length[j] + 1 > length[i]: length[i] = length[j] + 1print(max(length))const [n, ...a] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // length[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이const length = new Array(n).fill(1);for (let i = 0; i < n; i++) { for (let j = 0; j < i; j++) { if (a[j] < a[i] && length[j] + 1 > length[i]) length[i] = length[j] + 1; }}console.log(Math.max(...length));import { readFileSync } from "node:fs";const [n, ...a]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // length[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이const length: number[] = new Array(n).fill(1);for (let i = 0; i < n; i++) { for (let j = 0; j < i; j++) { if (a[j] < a[i] && length[j] + 1 > length[i]) length[i] = length[j] + 1; }}console.log(Math.max(...length));import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); StringTokenizer st = new StringTokenizer(br.readLine()); int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken()); // length[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이 int[] length = new int[n]; int best = 0; for (int i = 0; i < n; i++) { length[i] = 1; for (int j = 0; j < i; j++) { if (a[j] < a[i] && length[j] + 1 > length[i]) length[i] = length[j] + 1; } best = Math.max(best, length[i]); } System.out.println(best); }}using System;using System.Linq; class Program{ static void Main() { int n = int.Parse(Console.ReadLine()); int[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); // length[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이 int[] length = new int[n]; for (int i = 0; i < n; i++) { length[i] = 1; for (int j = 0; j < i; j++) { if (a[j] < a[i] && length[j] + 1 > length[i]) length[i] = length[j] + 1; } } Console.WriteLine(length.Max()); }}#include <algorithm>#include <iostream>#include <vector> int main() { int n; std::cin >> n; std::vector<int> a(n); for (int& x : a) std::cin >> x; // length[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이 std::vector<int> length(n, 1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a[j] < a[i] && length[j] + 1 > length[i]) length[i] = length[j] + 1; } } std::cout << *std::max_element(length.begin(), length.end()) << '\n';}#include <stdio.h> #define MAXN 2000 int main(void) { static int a[MAXN], length[MAXN]; int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); /* length[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이 */ int best = 0; for (int i = 0; i < n; i++) { length[i] = 1; for (int j = 0; j < i; j++) { if (a[j] < a[i] && length[j] + 1 > length[i]) length[i] = length[j] + 1; } if (length[i] > best) best = length[i]; } printf("%d\n", best); return 0;}n = 콘솔.줄읽기().수로변환();a = 콘솔.수들읽기();// len[i] = a[i]로 끝나는 가장 긴 증가 부분 수열의 길이len = 새목록(n, 1);best = 1;반복 (i = 1; i < n; i++){ 반복 (j = 0; j < i; j++) { 만약 (a[j] < a[i] && len[j] + 1 > len[i]) { len[i] = len[j] + 1; } } 만약 (len[i] > best) { best = len[i]; }}콘솔.쓰기(best);