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 = 99999999;

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

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

 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; 
}


위 코드로 통과되긴 했는데 이해가 안되는게


높이를 구하는 부분임


dfs(s + 1, i - 1) + dfs(i + 1, e) + (i - s) + depth(s, i) * 2;


여기서 depth(s, i) 이부분이 높이를 구하는 부분인데


s,i를 연결할때 높이를 구하려면 s~i 구간 안에 연결이 몇 개가 어떤 식으로 되어있는지 알아야 가능하다고 생각했음


그런데 위 얘기는 모순되는게 s~i구간 안의 모든 연결 조합을 비교한후 길이가 최소인 조합으로 연결해야 되잔아


그럼 결국에 조합을 모두 비교해보려면 각각 연결의 높이*2+가로를 알아야되는데 이 계산에서 필요한 높이를 알려면


모든 조합을 비교해봐야만 알수있다는거지(직관적으로 생각하면)


높이를 모르는데 조합을 해볼수가 없잔아.


위 코드는 그냥 높이를 s,i에서 존재할수 있는 가장 낮은 높이로 정의해서 풀었는데 통과가 됐어


그럼 결론은 s,i를 연결할때 그 안의 연결 조합이 어떻게 되든 s,i의 높이는 s,i를 연결할때 존재할수 있는 최소 높이란건데


위 문제를 풀땐 이걸 수학적으로 증명해서 풀어야 되는거임? 이걸 어떻게 알아내지?