[2216] 문자열과 점수

http://boj.kr/2216

d[i][j] = s의 i번째 문자열까지, t의 j번째 문자열까지의 최대 점수

< AC 코드 >

#include <stdio.h>
#include <string.h>
#define mINF 0x80000000
 
int a, b, c;
int slen, tlen;
char s[3005], t[3005];
int d[3005][3005];
 
int max(int x, int y)
{
    return x > y ? x : y;
}
 
int go(int si, int ti)
{
    int ret = mINF;
    if(d[si][ti]!=mINF) return d[si][ti];
 
    if(si == slen) return b * (tlen-ti);
    if(ti == tlen) return b * (slen-si);
 
    if(s[si] == t[ti])
        ret = max(ret, go(si+1, ti+1)+a);
    if(s[si] != t[ti])
        ret = max(ret, go(si+1, ti+1)+c);
    ret = max(ret, go(si+1, ti)+b);
    ret = max(ret, go(si, ti+1)+b);
    return d[si][ti] = ret; 
}
 
int main()
{
    int i, j;
    scanf("%d%d%d%s%s", &a, &b, &c, s, t);
    slen = strlen(s);
    tlen = strlen(t);
    for(i=0; i<3005; i++) for(j=0; j<3005; j++) d[i][j] = mINF;
    printf("%d\n", go(0, 0)); 
    return 0;
}
 

>> 0x8000000 : int 의 최소값이다.

>> 무조건 위에서 아래로 가도록 짜진 말아야겠다...

< 틀린 코드 >

#include <stdio.h>
#include <string.h>
#define mINF 0x80000000
 
int a, b, c;
char s[3005], t[3005];
int d[3005][3005];
 
int max(int x, int y)
{
    return x > y ? x : y;
}
 
int go(int si, int ti)
{
    int ret = mINF;
    if(si < 0) return b * (ti-1); 
    if(ti < 0) return b * (si-1);
    if(d[si][ti]!=mINF) return d[si][ti];
 
    if(s[si] == t[ti])
        ret = max(ret, go(si-1, ti-1)+a);
    if(s[si] != t[ti])
        ret = max(ret, go(si-1, ti-1)+c);
    ret = max(ret, go(si-1, ti)+b);
    ret = max(ret, go(si, ti-1)+b);
    return d[si][ti] = ret; 
}
 
int main()
{
    int i, j;
    scanf("%d%d%d%s%s", &a, &b, &c, s, t);
    for(i=0; i<3005; i++) for(j=0; j<3005; j++) d[i][j] = mINF;
    printf("%d\n", go(strlen(s)-1, strlen(t))-1); 
    return 0;
}
 

>> 점화식은 맞는데, 18%에서 틀렸다고 한다. 왜 틀린건지 모르겠다...ㅜㅜ

>> 17, 18 에서의 탈출조건도 ti+1, si+1 인거 같은데, 이렇게 하면 테케도 통과를 못한다...

>> 위 코드에 대한 반례

5 -3 -6 

a 

b

>> 정답코드에서는 -6이, 위 코드에서는 -4가 나온다...