문제

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=976&sca=3050


내가 짠 소스 오답=====================================

#include <stdio.h>

int N;
char point[101];
int w[101][101] = { 0, }, node[101], h[101][101] = { 0, };

int dfs(int s, int e){
 if (w[s][e] != 0)return w[s][e];
 if (s >= e)return 0;

 int i, j, S = 0, E = 0, temp, result = 9999999;

 for (i = s + 1; i <= e; i = i + 2){
  if (point[s] != point[i]){
   temp = dfs(s + 1, i - 1) + dfs(i + 1, e) + (i - s) + depth(s, i) * 2;

   if (result > temp){
    result = temp;
    S = s;
    E = i;
   }
  }
 }
 for (i = s + 1; i < e; i = i + 2){
  temp = dfs(s, i) + dfs(i + 1, e);
  if (result > temp){
   result = temp;
   S = s;
   E = i;
  }
 }
 if (result != 9999999)node[S + 1] = E + 1;
 return w[s][e] = result;
}

int depth(int s, int e){
 if (h[s][e] != 0)return h[s][e];
 if (s >= e)return 0;
 int i, j, temp, temp1, result = 9999999,result1=-1;

 for (i = s + 1; i <= e; i = i + 2){
  if (point[s] != point[i]){
   temp = depth(s + 1, i - 1)+1;
   if (result > temp){
    result = temp;
   }
  }
 }
 
 for (i = s + 1; i < e; i = i + 2){

  temp = depth(s, i);
  if (result1 < temp)result1 = temp;
  temp = depth(i + 1, e);
  if (result1 < temp)result1 = temp;
  if (result > result1){
   result = result1;
  }
 }
 
 

 return h[s][e] = result;
}


int main(void) {
 scanf("%d",&N);
 scanf("%s", &point);
 printf("%d\n",dfs(0, N-1));
 for (int i = 1; i <= N; i++){
  if (node[i] != 0){
   printf("%d %d\n", i, node[i]);
  }
  node[node[i]] = 0;

 }
 
 return 0; 
}


dp 소스 정답 ===================================================

#include<stdio.h>
#include<string.h>
#define MAX_N 200
#define BIG(a,b)(a>b?a:b)

int n;
char arr[MAX_N];

int d[MAX_N][MAX_N];
int h[MAX_N][MAX_N];
int back[MAX_N][MAX_N];

FILE *fp=fopen("input.txt","r");
FILE *cp=fopen("output.txt","w");

void process () {
 int i, j, k, l;
 for( i = 0; i < n; i++ )
  d[i][i] = 999999999;
 for( l = 1; l < n; l++ ) {
  for( i = 0; i < n-l; i++ ) {
   j = i + l;
   d[i][j] = 999999999;
   for( k = i+1; k <= j; k++ ) {
    if( arr[i] != arr[k] ) {
     if( d[i+1][k-1] + d[k+1][j] + (k-i) + 2 * (h[i+1][k-1] + 1) < d[i][j] ) {
      d[i][j] = d[i+1][k-1] + d[k+1][j] + (k-i) + 2 * (h[i+1][k-1] + 1);
      h[i][j] = BIG(h[i+1][k-1]+1,h[k+1][j]);
      back[i][j] = k;
     }
    }
   }
  }
 }
}
void recur(int v, int e) {
 if( v >= e ) return;
 fprintf(cp,"%d %d\n",v+1,back[v][e]+1);
 recur(v+1,back[v][e]-1);
 recur(back[v][e]+1,e);
}
void main() {
 char tmp;
 fscanf(fp,"%d%c",&n,&tmp);
 fgets(arr,255,fp);
 process ();
 fprintf(cp,"%d\n",d[0][n-1]);
 recur(0,n-1);
 fcloseall();
}



저 dp를 재귀호출로 어케 짜야될지 모르겟음 ㅠㅠ