https://www.acmicpc.net/problem/2550
2550번: 전구
첫 번째 줄에는 스위치의 수(전구의 수)를 나타내는 정수 N (1≤N≤10,000)이 주어진다. 두 번째 줄에는 N개의 스위치 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다. 세 번째 줄에는 N
www.acmicpc.net
[난이도] Gold4
[유형] DP
[풀이]
LIS DP 알고리즘을 이용해서 풀 수 있다.
#include <cstdio> #include <vector> #include <algorithm> using namespace std; int N,a[10001],b[10001],c[10002],dp[10002]; pair<int,int> trc[10001]; int main(){ scanf("%d",&N); for(int i=1;i<=N;i++){ int v; scanf("%d",&v); a[v]=i; } for(int i=1;i<=N;i++) scanf("%d",&b[i]); for(int i=1;i<=N;i++) c[a[b[i]]]=i; vector<int> v; for(int i=1;i<=N;i++){ int j = lower_bound(v.begin(),v.end(),c[i])-v.begin(); if(j<v.size()) v[j]=c[i]; else v.push_back(c[i]); trc[i]={j,c[i]}; } int j=v.size()-1; vector<int> l; for(int i=N;i>0;i--){ if(trc[i].first==j){ l.push_back(trc[i].second); j--; } } printf("%d\n",l.size()); for(auto& p : l) p = b[p]; sort(l.begin(),l.end()); for(auto& p : l) printf("%d ",p); }
https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2550.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold4] 20058 : 마법사 상어와 파이어스톰 (C++) (0) | 2021.02.14 |
|---|---|
| [BOJ/백준][Gold4] 12970 : AB (C++) (0) | 2021.02.14 |
| [BOJ/백준][Gold4] 3908 : 서로 다른 소수의 합 (C++) (0) | 2021.02.06 |
| [BOJ/백준][Gold4] 20040 : 사이클게임 (C++) (0) | 2021.02.06 |
| [BOJ/백준][Gold4] 16172 : 나는 친구가 적다(large) (C++) (0) | 2021.02.06 |