1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| #include <iostream>
#include <cstring>
#define MAX_COMMAND 1000000
using namespace std;
int command[MAX_COMMAND];
int numOfCommand;
int foot[2];
int dp[5][5][MAX_COMMAND];
int getMinEnergy(int cmd);
int min(int a, int b) {
return a < b ? a : b;
}
bool isClose(int f, int cmd);
bool isOpposite(int f, int cmd);
int main() {
while (true) {
cin >> command[numOfCommand];
if (command[numOfCommand] == 0)
break;
numOfCommand++;
}
cout << getMinEnergy(0);
}
int getMinEnergy(int cmd) {
if (cmd == numOfCommand)
return 0;
if (dp[foot[0]][foot[1]][cmd] != 0)
return dp[foot[0]][foot[1]][cmd];
int minimum = 2000000000;
//같은 자리에 있는 발이 있는지 검사
if (command[cmd] == foot[0] || command[cmd] == foot[1]) {
minimum = min(minimum, getMinEnergy(cmd + 1) + 1);
}
else {
//중앙에 있는 지 확인
if (foot[0] == 0) {
foot[0] = command[cmd];
minimum = min(minimum, getMinEnergy(cmd + 1) + 2);
foot[0] = 0;
}
if (foot[1] == 0) {
foot[1] = command[cmd];
minimum = min(minimum, getMinEnergy(cmd + 1) + 2);
foot[1] = 0;
}
int tempLeft = foot[0];
int tempRight = foot[1];
//인접한지 확인
if (isClose(foot[0], command[cmd])) {
foot[0] = command[cmd];
minimum = min(minimum, getMinEnergy(cmd + 1) + 3);
foot[0] = tempLeft;
}
if (isClose(foot[1], command[cmd])) {
foot[1] = command[cmd];
minimum = min(minimum, getMinEnergy(cmd + 1) + 3);
foot[1] = tempRight;
}
//반대편으로
if (isOpposite(foot[0], command[cmd])) {
foot[0] = command[cmd];
minimum = min(minimum, getMinEnergy(cmd + 1) + 4);
foot[0] = tempLeft;
}
if (isOpposite(foot[1], command[cmd])) {
foot[1] = command[cmd];
minimum = min(minimum, getMinEnergy(cmd + 1) + 4);
foot[1] = tempRight;
}
}
return dp[foot[0]][foot[1]][cmd] = minimum;
}
bool isClose(int f, int cmd) {
if (f == 1 && (cmd == 2 || cmd == 4))
return true;
if (f == 2 && (cmd == 1 || cmd == 3))
return true;
if (f == 3 && (cmd == 2 || cmd == 4))
return true;
if (f == 4 && (cmd == 1 || cmd == 3))
return true;
return false;
}
bool isOpposite(int f, int cmd) {
if (f == 1 && cmd == 3)
return true;
if (f == 2 && cmd == 4)
return true;
if (f == 3 && cmd == 1)
return true;
if (f == 4 && cmd == 2)
return true;
return false;
}
|
