BOJ 1155 - 변형 하노이

BOJ 1155 - 변형 하노이

문제가 설명이 좀 부족하긴 한데,

$dp_{n,f,t}=\text{f에 n개가 쌓여 있을 때 f에서 t로 보내기 위한 최소 개수}$ 라고 해보자.

항상 $n=1 \Rightarrow dp_{n,f,t}$ 이다.

라고 생각하면 문제를 이미 틀렸다.

사실 $f$와 $t$에 따라 $n=1$ 이여도 아예 움직일 수가 없어서 답이 불가능한 경우가 생긴다.

예를 들어, $AB > AC$ 인데 우린 $A \to C$를 가야한다고 하면 $C$ 로 먼저가면 조건 1에 의해 더 못움직여서 답이 없다.

여하튼 $n=1$ 인 경우에 우선순위를 잘 보고 가능한지 불가능한지를 판단하는 로직을 짯다고 하자.

$n \ge 2$ 에서는 다음과 같은 점화식이 성립한다. $k$ 를 3개의 폴 중 $f$나 $t$가 아닌 나머지 하나라고 할 때,

$$ dp_{n,f,t}=Min\begin{cases} \large dp_{n-1,f,k}+1+dp_{n-1,k,t} \\\\ \large dp_{n-1,f,t}+1+dp_{n-1,t,f}+1+dp_{n-1,f,t} \end{cases} $$

중간에 1씩 더해주는건 가장 큰 원판을 옮기는 것이라고 생각하면 된다.

가장 큰 원판을 옮기는 연산들에 대해서 $dp_1$ 의 값을 사용해줄 필요가 없는 것은 저 때는 우선순위가 어떻게 되든 조건 1에 따라서 큰 원판을 다른 나머지 한 칸으로 옮길 수 밖에 없기 때문이다.

$dp_1$ 에서 우선순위에 의해 불가능한 조건들을 $\infty$ 라고 설정하면 문제가 해결된다.

vs p(6);  
int n, dp[40][4][4];  
  
bool prior(string a, string b) {  
   return find(all(p), a) < find(all(p), b);  
}  
  
const int inf = 1e18;  
int fn(int i, int a, int b) {  
   if (i == 1) {  
      if (a == 1) {  
         if (b == 2) {  
            if (prior("AB", "AC")) return 1;  
            return inf;  
         }  
         if (b == 3) {  
            if (prior("AC", "AB")) return 1;  
            return inf;  
         }  
      }  
      if (a == 2) {  
         if (b == 1) {  
            if (prior("BA", "BC")) return 1;  
            return inf;  
         }  
         if (b == 3) {  
            if (prior("BC", "BA")) return 1;  
            return inf;  
         }  
      }  
      if (a == 3) {  
         if (b == 1) {  
            if (prior("CA", "CB")) return 1;  
            return inf;  
         }  
         if (b == 2) {  
            if (prior("CB", "CA")) return 1;  
            return inf;  
         }  
      }  
   }  
   int &ret = dp[i][a][b];  
   if (~ret) return ret;  
  
   int c = 6 - a - b;  
   return ret = min({  
                       inf,  
                       fn(i - 1, a, c) + 1 + fn(i - 1, c, b),  
                       fn(i - 1, a, b) + 1 + fn(i - 1, b, a) + 1 + fn(i - 1, a, b),  
                    });  
};

void solve() {  
   cin >> n;  
   fv(p);  
   memset(dp, -1, sizeof dp);  
   cout << min(fn(n, 1, 2), fn(n, 1, 3));  
}