Mosu(정종인)
2020. 1. 21. 13:39
반응형
- 복습
boj.kr/13301, boj.kr/17391
- LCS(Longest Common Subsequence)
ACAYKP, CAPCAK이 있을 때 최장 공통 부분 문자열을 구해보자.
A | C | A | Y | K | P | |
---|---|---|---|---|---|---|
C | 0 | 1 | 1 | 1 | 1 | 1 |
A | 1 | 1 | 2 | 2 | 2 | 2 |
P | 1 | 1 | 2 | 2 | 2 | 3 |
C | 1 | 2 | 2 | 2 | 2 | 3 |
A | 1 | 2 | 3 | 3 | 3 | 3 |
K | 1 | 2 | 3 | 3 | 4 | 4 |
dp[i][j] = 첫번째 문자열의 i번째, 두번째 문자열의 j번째까지 봤을 때 가장 긴 공통 부분 문자열
arr[i] == arr[j] 일 때 dp[i][j] = dp[i-1][j-1] + 1;
arr[i] != arr[j] 일 때 dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
참고 문제 : boj.kr/9251, boj.kr/3793, boj.kr/5582, boj.kr/5502, boj.kr/1695, boj.kr/1958, boj.kr/9252, boj.kr/14002/, boj.kr/12852
- 부록 : 참고 문제 풀이
- boj.kr/13301
#include <iostream>
using namespace std;
typedef long long int ll;
ll arr[100];
ll dp[100];
int main(){
ll N; cin >> N;
arr[1]=1;
arr[2]=1;
dp[1]=4;
dp[2]=6;
for(int i=3; i<=N; ++i){
arr[i]=arr[i-1]+arr[i-2];
dp[i]=dp[i-1]+arr[i]*2;
}
cout << dp[N] << '\n';
}
- boj.kr/17391
#include <iostream>
using namespace std;
int arr[301][301];
int dp[301][301];
int main(){
int N, M; cin >> N >> M;
dp[1][1] = 0;
for(int i=1; i<=N; ++i){
for(int j=1; j<=M; ++j){
cin >> arr[i][j];
int res=987654321;
for(int k=1; k<=i-1; ++k){
if(k+arr[k][j]>=i) res=min(res, dp[k][j]+1);
}
for(int k=1; k<=j-1; ++k){
if(k+arr[i][k]>=j) res=min(res, dp[i][k]+1);
}
if(!(i==1 && j==1)) dp[i][j]=res;
}
}
cout << dp[N][M] << '\n';
}
//dp[i][j] = i, j가 도착 지점일 때 부스터의 최소 개수
//dp[i][j] = min(dp[1~i-1][j]+1, dp[i][1~j-1]+1), 단, 이동 가능해야 함.
- boj.kr/9251
#include <iostream>
#include <string>
using namespace std;
int dp[4001][4001];
int main(){
string a, b; cin >> a >> b;
for(int i=0; i<a.size(); ++i){
for(int j=0; j<b.size(); ++j){
if(a[i] == b[j]) dp[i+1][j+1] = dp[i][j]+1;
else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
}
}
cout << dp[a.size()][b.size()] << '\n';
}
- boj.kr/3793
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int dp[4001][4001];
int main(){
char a[1000], b[1000];
while(scanf("%s %s", a, b) != EOF){
for(int i=0; i<=4000; ++i){
for(int j=0; j<=4000; ++j){
dp[i][j] = 0;
}
}
for(int i=0; a[i]!=0; ++i){
for(int j=0; b[j]!=0; ++j){
if(a[i] == b[j]) dp[i+1][j+1] = dp[i][j]+1;
else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
}
}
cout << dp[strlen(a)][strlen(b)] << '\n';
}
}
- boj.kr/5582
#include <iostream>
#include <string>
using namespace std;
int dp[4001][4001];
int res=-1;
int main(){
string a, b; cin >> a >> b;
for(int i=0; i<a.size(); ++i){
for(int j=0; j<b.size(); ++j){
if(a[i] == b[j]) dp[i+1][j+1] = dp[i][j]+1;
else dp[i+1][j+1] = 0;
res=max(res, dp[i+1][j+1]);
}
}
cout << res << '\n';
}
- boj.kr/5502
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[5001][5001];
int main(){
int N; cin >> N;
string a; cin >> a;
string b=a;
reverse(b.begin(), b.end());
for(int i=0; i<a.size(); ++i){
for(int j=0; j<b.size(); ++j){
if(a[i] == b[j]) dp[i+1][j+1] = dp[i][j]+1;
else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
}
}
cout << a.size()-dp[a.size()][b.size()] << '\n';
}
- boj.kr/1695
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[5001][5001];
int a[5001];
int b[5001];
int main(){
int N; cin >> N;
for(int i=1; i<=N; ++i){
cin >> a[i];
b[N-i+1] = a[i];
}
for(int i=1; i<=N; ++i){
for(int j=1; j<=N; ++j){
if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
}
}
cout << N-dp[N][N] << '\n';
}
- boj.kr/1958
#include <iostream>
#include <string>
#define max6(a, b, c, d, e, f) max((a), max((b), max((c), max((d), max((e), (f))))))
using namespace std;
int dp[101][101][101];
int main(){
string a, b, c; cin >> a >> b >> c;
for(int i=1; i<=a.size(); ++i){
for(int j=1; j<=b.size(); ++j){
for(int k=1; k<=c.size(); ++k){
if(a[i-1] == b[j-1] && b[j-1] == c[k-1]) dp[i][j][k] = dp[i-1][j-1][k-1]+1;
else dp[i][j][k] = max6(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1], dp[i-1][j-1][k], dp[i][j-1][k-1], dp[i-1][j][k-1]);
}
}
}
cout << dp[a.size()][b.size()][c.size()] << '\n';
}
- boj.kr/9252
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[4001][4001];
string res = "";
int main(){
string a, b; cin >> a >> b;
for(int i=0; i<a.size(); ++i){
for(int j=0; j<b.size(); ++j){
if(a[i] == b[j]) dp[i+1][j+1] = dp[i][j]+1;
else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
}
}
cout << dp[a.size()][b.size()] << '\n';
int i=a.size(), j=b.size();
while(1) {
if(dp[i][j] == 0) break;
if(dp[i-1][j] == dp[i][j]){
i-=1;
continue;
}
if(dp[i][j-1] == dp[i][j]) {
j-=1;
continue;
}
res+=a[i-1];
i-=1; j-=1;
}
reverse(res.begin(), res.end());
cout << res << '\n';
}
- boj.kr/14002
#include <iostream>
#include <vector>
using namespace std;
int arr[1001];
int dp[1001];
int maxcnt=-1;
vector<int> v;
int main(){
int N; cin >> N;
for(int i=1; i<=N; ++i){
cin >> arr[i];
if(i==1) dp[i]=1;
int res=1;
for(int j=1; j<i; ++j){
if(arr[i]>arr[j]) res=max(res, dp[j]+1);
}
dp[i]=res;
maxcnt=max(dp[i], maxcnt);
}
cout << maxcnt << '\n';
int key=maxcnt;
for(int i=N; i>=1; --i){
if(key==0) break;
if(dp[i] == key) {
v.push_back(arr[i]);
key--;
}
}
for(int i=v.size()-1; i>=0; --i){
cout << v[i] << " ";
}
cout << '\n';
}
- boj.kr/12852
#include <iostream>
#include <string>
using namespace std;
int dp[1000001];
int solve(int n){
if(dp[n]) {
return dp[n];
}
if(n==1) {
return 0;
}
if(n%3==0){
if(n%2==0){
return dp[n]=min(solve(n/3), min(solve(n/2), solve(n-1)))+1;
}
else {
return dp[n] = min(solve(n/3), solve(n-1))+1;
}
}
else if(n%2==0) {
return dp[n] = min(solve(n/2), solve(n-1))+1;
}
else return dp[n] = solve(n-1)+1;
}
int main(){
int N; cin >> N;
cout << solve(N) << '\n';
while(N!=1) {
if(N%3==0 && dp[N]==dp[N/3]+1){
cout << N << ' ';
N/=3;
}
else if(N%2==0 && dp[N] == dp[N/2]+1) {
cout << N << ' ';
N/=2;
}
else{
cout << N << ' ';
N-=1;
}
}
cout << "1" << '\n';
}
반응형