백준 2035, DP
정해가 2개 이상인 문제다.
나는 DP로 풀었지만, 원본 solution 작성자들은 backtracking + (smart) bruteforce 를 이용했다.
DP 점화식 : f(i,j) : 길이 j+1인 string 에서 suffix가 i 번째부터 시작할 때, 증가 수열을 만들 수 있는가?
아래는 대회 출제자 힌트의 일부.
A backtracking algorithm will work here as the numbers grow fast enough that the branching factor is not too bad. The tricky part comes in handling the 0's (which gave all of the judges fits). A dynamic programming approach will also work,but two passes are necessary: one to get the smallest last number, then another to resolve the tie-breaker.
DP에 tie-breaker가 딱히 필요없다는게 포인트. 디버깅이 어려웠다.
점점 무뎌지는 감각이 야속하다.
Source Code
// https://www.acmicpc.net/problem/2035
// https://www.acmicpc.net/problem/1011
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
using namespace std;
string input, MAXI;
bool cmp(string a, string b){
// true if a>b
int alen,blen;
alen = a.length();
blen = b.length();
int astart = 0,bstart = 0;
for(int i=0;i<alen;++i){
if(a[i] != '0'){
astart = i;
break;
}
}
for (int i = 0; i < blen; ++i) {
if (b[i] != '0') {
bstart = i;
break;
}
}
if (alen - astart > blen - bstart) return true;
if (alen - astart < blen - bstart) return false;
bool chk = false;
for (int i = 0; i < alen - astart;++i){
if(a[astart + i] > b[bstart + i]){
chk = true;
break;
}
if (a[astart + i] < b[bstart + i]) {
chk = false;
break;
}
}
return chk;
}
int dp[85][85];
int solve(int i, int j){
if(dp[i][j]!=-1) return dp[i][j];
if(i==0){
dp[i][j] = 1;
return dp[i][j];
}
dp[i][j] = 0;
for(int k=0;k<i;++k){
int chk = solve(k,i-1);
if(chk == 1){
if (cmp(input.substr(i, j - i + 1), input.substr(k, i - k))) dp[i][j] = 1;
}
}
return dp[i][j];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> input;
MAXI = "";
for(int i=0;i<85;++i){
MAXI += "9";
}
for (int i = 0; i < 85; ++i) {
for(int j=0;j<85;++j){
dp[i][j] = -1;
}
}
int l = input.length();
for(int i=l-1;i>=0;--i){
if(solve(i,l-1)){
//cout << input.substr(i, l-i) << "\n";
if (cmp(MAXI, input.substr(i, l - i))) MAXI = input.substr(i, l - i);
}
}
//cout << "MAXI: " << MAXI;
bool chk = false;
for(int i=0;i<MAXI.length();++i){
if(MAXI[i] != '0') chk = true;
if(chk) cout << MAXI[i];
}
return 0;
}
/*
//below are archive of official judge solutions
//backtrack, dp, etc.
#include <iostream.h>
#define SIZE 1000
bool commas[SIZE];
int lastComma, lastSize;
bool greater(int prev, int start, int end, int a[])
{
int prevend = start;
while (start < end && a[start] == 0)
start++;
if (start == end && a[start] == 0)
return false;
while (prev < prevend-1 && a[prev] == 0)
prev++;
if (prev == prevend-1 && a[prev] == 0)
return true;
if (prevend-prev > end-start+1)
return false;
if (prevend-prev < end-start+1)
return true;
for(int i=start; i<=end; i++) {
if (a[i] > a[i-start+prev])
return true;
else if (a[i] < a[i-start+prev])
return false;
}
return false;
}
bool greaterequal(int start1, int end1, int start2, int end2, int a[])
{
bool iszero1 = false, iszero2 = false;
while (start1 < end1-1 && a[start1] == 0)
start1++;
if (start1 == end1-1 && a[start1] == 0)
iszero1 = true;
while (start2 < end2-1 && a[start2] == 0)
start2++;
if (start2 == end2-1 && a[start2] == 0)
iszero2 = true;
if (end1-start1 > end2-start2)
return true;
if (end1-start1 < end2-start2)
return true;
for(int i=start1; i<end1; i++) {
if (a[i] > a[i-start1+start2])
return true;
else if (a[i] < a[i-start1+start2])
return false;
}
return true;
}
void findseries(int start, int a[], int size, int prev, bool comma[])
{
if (start == size) {
if (greaterequal(prev, size, lastComma, size, a)) {
for(int i=0; i<size; i++)
commas[i] = comma[i];
lastComma = prev;
int temp = prev;
lastSize = size-prev;
}
return;
}
comma[start-1] = true;
int i=start;
while (i<size && !greater(prev, start, i, a)) {
i++;
}
int j = start;
while (j<i && a[j] == 0)
j++;
while (i<size && (i-j+1 <= lastSize)) {
findseries(i+1, a, size, start, comma);
i++;
}
comma[start-1] = false;
}
int main()
{
int size;
int a[SIZE];
bool comma[SIZE];
char ch;
while (true) {
for(size=0; true; size++) {
cin.get(ch);
if (ch < '0' || ch > '9')
break;
a[size] = ch-'0';
comma[size] = false;
commas[size] = false;
}
if (size == 1 && a[0] == 0)
break;
lastComma = 0, lastSize = size;
int i=1;
while (i<size) {
findseries(i, a, size, 0, comma);
i++;
}
bool nonzero = false;
for(i=0; i<size; i++) {
cout << a[i];
if (a[i] != 0)
nonzero = true;
if (nonzero && commas[i]) {
cout << ',';
nonzero = false;
}
}
cout << endl;
}
}
///////////////////////////////////
//increasing.cpp
//increasing sequence problem
//pgmr: T Feil
#include <iostream.h>
#include <string.h>
char S[81];
int first, n, TheBest[81], Best[81], Mark[81];
//copy S[n..n+k-1] to T[]
void SubstringCopy(char S[81], char T[81], int n, int k) {
int i;
for(i=n;i<n+k;i++)
T[i-n]=S[i];
T[k]='\0';
}
//true is S>T (as numbers)
int Bigger(char S[81], char T[81]){
int n, m, i, j;
if(T[0]=='\0') return 1;
n=strlen(S);
m=strlen(T);
i=0;
while(S[i]=='0') i++;
n=n-i;
j=0;
while(T[j]=='0') j++;
m=m-j;
if(n>m) return 1;
if(n<m) return 0;
while(S[i]!='\0' && S[i]==T[j]){
i++; j++;
}
if(S[i]=='\0') return 0;
if(S[i]>T[j]) return 1;
return 0;
}
void Copy(int A[81], int B[81],int n){
int i;
for(i=0;i<=n;i++) A[i]=B[i];
}
void PrintSeq(){
int i, first=1;
for(i=0;i<n;i++){
cout<<S[i];
if(TheBest[i])
cout<<',';
}
cout<<endl;
}
int FirstWord(int start, int finish, char* prev, int last){
char F[81],T[81],Last[81];
int newfinish,length=n-last;
while(finish>=start &&finish<last){
SubstringCopy(S,F,start,finish-start+1);
SubstringCopy(S,Last,last,n-last);
if(Bigger(F,prev) && Bigger(Last,F)){
if(finish==last-1){ //got a solution
Best[finish]=1;
return 1;
}
else{
SubstringCopy(S,T,start,finish-start+1);
if(FirstWord(finish+1,last-1,T,last)){
Best[finish]=1;
return 1;
}
}
}
finish--;
}
return 0;
}
int BiggerSeq(int A[], int B[]){
int i, Afirst = -1, Bfirst=-1, Alast, Blast;
char Anum[81], Bnum[81];
Alast=Blast=0;
while(Alast<n && Blast <n) {
Alast = Afirst+1;
Blast = Bfirst+ 1;
while(Alast<n && A[Alast]==0)
Alast++;
while(Blast<n && B[Blast]==0) Blast++;
SubstringCopy(S,Anum, Afirst+1,Alast-Afirst);
SubstringCopy(S,Bnum, Bfirst+1,Blast-Bfirst);
//cout<<Anum<<' '<<Bnum<<endl;
if(Bigger(Anum,Bnum))
return 1;
if(Bigger(Bnum,Anum))
return 0;
Afirst=Alast;
Bfirst=Blast;
}
return 0;
}
void UpDate(){
int i;
//cout<<"UpDate"<<endl;
//for(i=0;i<n;i++) cout<<Best[i]; cout<<endl;
if(first){
first=0;
for(i=0;i<n;i++)
TheBest[i]=Best[i];
}
else
if(BiggerSeq(Best,TheBest))
for(i=0;i<n;i++)
TheBest[i]=Best[i];
}
void main(){
int i,last,newlast,found,finish;
cin>>S;
n=strlen(S);
while(n!=1 || S[0]!='0'){
for(i=0;i<n;i++){ TheBest[i]=0; Mark[i]=0;}
last=n-1;
found =0;
first=1;
while(last>-1 && !found){
newlast=last;
while(newlast>0 && S[newlast-1]=='0') newlast--;
if(newlast==0) found=1;
else{
while(newlast<=last){
for(i=0;i<n;i++) Best[i]=0;
finish=n-newlast-1;
if(finish>=newlast) finish=newlast-1;
if(FirstWord(0,finish,"0",newlast)){
found=1;
UpDate();
}
finish++;
newlast++;
}
}
last--;
}
PrintSeq();
cin>>S;
n=strlen(S);
}
}
///////////////////////////
/* Solution to increasing sequences, revised 8/21/02 to fix "leading
zeros"
Bob Roos
#include <stdio.h>
#include <string.h>
char digits[81]; /* input digits
int length; /* length of "
int found;
char sequence[80][81]; /* reverse of sequence currently being tested
int seqlength; /* length of " " "
char bestseq[80][81]; /* best sequence found so far (reversed)
int bestseqlength; /* length of " " "
/* compare two strings numerically/lexicographically (e.g.,
00062 < 814, 28193283 < 00030000000, etc.)
int compare(char *first, char *second)
{
char temp1[81], temp2[81];
int i,maxlength;
for (i = 0; i < 80; i++)
{
temp1[i] = '0';
temp2[i] = '0';
}
temp1[80] = 0;
temp2[80] = 0;
/* pad the shorter one with zeros on the left so both have
same length:
maxlength = strlen(first);
if (strlen(first) < strlen(second))
{
maxlength = strlen(second);
}
strcpy(temp1+(maxlength-strlen(first)),first);
strcpy(temp2+(maxlength-strlen(second)),second);
return strcmp(temp1,temp2);
}
/* print out the final answer
void printanswer()
{
int i;
for (i = bestseqlength-1; i >= 1; i--)
printf("%s,",bestseq[i]);
printf("%s\n",bestseq[0]);
}
/* Compare current backtrack solution to best found so far
void updatebest()
{
int i,j,k;
i = seqlength-1;
j = bestseqlength-1;
while (i > 0 && j > 0 && compare(sequence[i],bestseq[j]) == 0)
{
i--;
j--;
}
if (bestseqlength <= 0 || compare(sequence[i],bestseq[j]) > 0)
{
for (k = 0; k < seqlength; k++)
strcpy(bestseq[k],sequence[k]);
bestseqlength = seqlength;
}
}
/* Do the backtracking search
void backtrack()
{
int i;
/* base case: see if digits string is empty:
if (strlen(digits) <= 0)
{
found = 1;
updatebest();
return;
}
/* Otherwise, try every viable suffix, from longest to shortest.
"Viable" means suffix value is less than last element in sequence.
i = strlen(digits) - 1; /* start with final unused digit
while (i >= 0 && compare(digits+i,sequence[seqlength-1]) < 0)
i--;
i++;
/* Check for failure (unable to find smaller value):
while (i < strlen(digits))
{
strcpy(sequence[seqlength++],digits+i);
digits[i] = 0;
backtrack();
/* restore deleted digit:
digits[i] = sequence[seqlength-1][0];
--seqlength;
i++;
}
return;
}
void solve()
{
int i;
found = 0;
bestseqlength = 0;
/* Try all suffixes, from shortest to longest:
for (i = strlen(digits) - 1; i >= 0; i--)
{
strcpy(sequence[0],digits+i);
seqlength=1;
/* "remove" suffix from string:
digits[i] = 0;
/* backtrack to find remaining elements in sequence
backtrack();
if(found && (i == 0 ||(i > 0 && digits[i-1] != '0')))
break;
/* restore old suffix
strcpy(digits+i,sequence[0]);
}
printanswer();
}
int main()
{
while(scanf("%s",digits))
{
if (strcmp(digits,"0") == 0)
break;
// printf("String is \"%s\"\n",digits);
solve();
}
}
/////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAX_LEN 80
char line[MAX_LEN+1];
int num_cmp(char *n1, int len1, char *n2, int len2)
{
for (; len1 > 1 && *n1 == '0'; n1++, len1--)
;
for (; len2 > 1 && *n2 == '0'; n2++, len2--)
;
if (len1 < len2) {
return -1;
} else if (len1 > len2) {
return 1;
} else {
while (len1 > 0) {
if (*n1 < *n2) {
return -1;
} else if (*n1 > *n2) {
return 1;
}
len1--;
len2--;
n1++;
n2++;
}
return 0;
}
}
int better(char *seq1, char *seq2)
{
char *p1, *p2;
int len1, len2, t;
if (*seq1 == ',') {
return better(seq1+1, seq2);
}
if (*seq2 == ',') {
return better(seq1, seq2+1);
}
if (!(*seq1) && !(*seq2)) {
return 0;
}
assert(*seq1 && *seq2);
p1 = strchr(seq1, ',');
p2 = strchr(seq2, ',');
len1 = (p1) ? p1 - seq1 : strlen(seq1);
len2 = (p2) ? p2 - seq2 : strlen(seq2);
t = num_cmp(seq1, len1, seq2, len2);
if (t < 0) {
return 0;
} else if (t > 0) {
return 1;
} else {
return better(seq1 + len1, seq2 + len2);
}
}
int read_case(void)
{
scanf("%s", line);
if (line[0] == '0' && strlen(line) == 1) {
return 0;
} else {
return 1;
}
}
void solve_case(void)
{
int best[MAX_LEN], best2[MAX_LEN];
char seq[2*MAX_LEN+1], best_seq[2*MAX_LEN+1];
int i, j, k, k1, k2, n, flag;
n = strlen(line);
/* first minimize last element
best[0] = 1;
for (i = 1; i < n; i++) {
best[i] = -1;
for (j = 1; j <= i && best[i] == -1; j++) {
k2 = i+1-j;
k1 = k2 - best[k2-1];
if (num_cmp(line+k1, best[k2-1], line+k2, j) < 0) {
best[i] = j;
}
}
if (best[i] == -1) {
best[i] = i+1;
}
}
flag = 0;
if (!num_cmp(line+n-best[n-1], best[n-1], line, n)) {
strcpy(best_seq, line);
flag = 1;
}
for (k = best[n-1]; k < n && !num_cmp(line+n-best[n-1], best[n-1],
line+n-k, k); k++) {
k1 = n-k-best[n-k-1];
if (num_cmp(line+k1, best[n-k-1], line+n-k, k) < 0) {
/* now go backward to break ties
best2[n-k] = k;
for (i = n-k; i >= 0; i--) {
for (j = 1; i+j <= n-k; j++) {
if (num_cmp(line+i, j, line+i+j, best2[i+j]) < 0) {
best2[i] = j;
}
}
}
for (i = k2 = 0; i < n; i += best2[i]) {
if (i) {
seq[k2++] = ',';
}
for (j = 0; j < best2[i]; j++) {
seq[k2++] = line[i+j];
}
}
seq[k2++] = 0;
if (!flag || better(seq, best_seq)) {
strcpy(best_seq, seq);
flag = 1;
}
}
}
assert(flag);
printf("%s\n", best_seq);
}
int main(void)
{
while (read_case()) {
solve_case();
}
return 0;
}
*/