[도전 27일차] 검은점과 하얀점 연결 풀이

※복습 : 

 

문제 : 백준 2647 검은점과 하얀점 연결

문제 링크

 

사용 알고리즘 : Dynamic Programming

 

풀이:

A[i] : i번째 점의 색깔 ( 0이면 하양, 1이면 검정 )

1. X[i][j] => i번점부터 j번점까지 검은 점의 개수

X[i][j]*2 == (j-i+1) 이면 i,j 가 연결이 가능하다.

X[i][j] = X[i][j-1] + A[j]로 구하기

그 다음 X[i][j]의 정의를 바꾸기

2. X[i][j] = i번점부터 j번까지 살펴보았을 때 i번점과 j번점의 개수가 같은가?

X[i][j] = ( X[i][j]*2 == (j-i+1) ) 로 갱신. 

 

DP[i][j] : i번점부터 j번점까지 보았을 때 최소 연결 거리

H[i][j] : i번점부터 j번점까지 보았을 때 최소 연결 거리를 가지는 경우의 높이

DP[i][j] = i<t<=j, A[t] != A[i], X[i+1][t-1]==1 , X[t+1][j]==1 인 모든 t에 대해 

DP[i+1][t-1] +2*(H[i+1][t-1]+1)+(t-i) + DP[t+1][j] 가 min인 t를 고르면 된다.

높이 : max(H[i+1][t-1] +1 , H[t+1][j] ) 로 갱신.

 

역추적이 관건이다. 재귀함수 형태가 역추적이 쉬울 것 같아 재귀로 구현했다.

처음에 배열 크기를 딱 맞게 101로 잡아서 몇번 WA를 받았다.

배열 초기화 값(0)을 이용한다면 무조건 배열 크기는 널널하게 N+10 정도로 잡는 습관을 들이자. 

 

 

 

코드

//howtoliveworldnice.tistory.com/117
#include<bits/stdc++.h>
const int INF = 1e9;
using namespace std;
int n,A[110],X[110][110],DT[110][110],H[110][110];
int C[110][110];
void input(){
    scanf("%d",&n); 
    for(int i=1;i<=n;i++)
        scanf("%1d",A+i);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n+1;j++)
            X[i][j]=X[i][j-1]+A[j];
    for(int i=1;i<n;i++)
        for(int j=i;j<=n;j++)
            X[i][j]=(X[i][j]*2 == (j-i+1));
    for(int i=1;i<=n+1;i++)
        X[i][i-1]=1;
}
int solve(int s,int e){
    if(s>=e) return 0;
    if(DT[s][e]) return DT[s][e];
    if(s+1==e){
        C[s][e]=e;
        H[s][e]=1;
        return DT[s][e]=3;
    }
    int ans=INF,ans_h,ans_id=-1,cal;
    for(int t=s+1;t<=e;t+=2){
        if(A[t]!=A[s] && X[s+1][t-1]){
            cal=solve(s+1,t-1)+2*(H[s+1][t-1]+1)+(t-s)+solve(t+1,e);
            if(cal<ans){
                ans=cal;
                ans_h=max(H[s+1][t-1]+1,H[t+1][e]);
                ans_id=t;
            }
        }
    }
    C[s][e]=ans_id;
    H[s][e]=ans_h;
    return DT[s][e]=ans;
}
void find(int s,int e){
    if(s>e || !C[s][e]) return;
    printf("%d %d\n",s,C[s][e]);
    find(s+1,C[s][e]-1);
    find(C[s][e]+1,e);
}
int main(){
    input();
    printf("%d\n",solve(1,n));
    find(1,n);
}

 

궁금한 점이 있으시다면 질문 남겨주세요 :)

하트와 댓글은 로그인 안해도 가능해요!