ARC 문제集中的 LIS 및 순열 복구 문제 풀이
CSP 제4회 모의고사 후기
이번 모의고사는 첫째 날 치러진 시험이었는데, 네 가지 사고력을 요구하는 문제가 등장했다. 각 문제의 풀이 과정을 정리해보았다.
문제 1: ARC125C - LIS를 원래 순열로 복구하기
주어진 수열에서 최장 증가 부분 수열(LIS)의 길이를 복원하여 사전식 순서가 가장 작은 원래 수열을 구하는 문제다. 핵심 아이디어는 그리디 알고리즘에 있다.
...
8월 30일 01:25에 게시됨
AtCoder ABC393 풀이: A~F번 문제 해석
A - Poisonous Oyster
문제 요약
두 사람 A, B가 4가지 음식 중 일부를 먹는다. A는 1, 2번을, B는 1, 3번을 먹는다. 각자의 상태(fine/sick)가 주어질 때, 어떤 음식이 독이 있는지 판별하라.
풀이
조건에 따라 직접 분기하면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr) ...
7월 5일 02:26에 게시됨
최장 증가 부분 수열의 응용 문제와 해결 전략
교차하지 않는 다리 건설 문제
강의 양안에 위치한 도시들을 연결하는 다리를 건설할 때 교차하지 않도록 최대 다리 수를 구하는 문제입니다. 하안 도시를 배열 인덱스로, 상안 도시 번호를 값으로 매핑하면 최장 증가 부분 수열(LIS) 문제로 변환됩니다. 도시 쌍을 정렬한 후 LIS 길이를 계산합니다.
#include <iostream>
#include <algorithm>
using namesp ...
7월 3일 03:26에 게시됨