D번은 참 각별한 인연이 있는 문제입니다. 바로 D가 저의 ICPC 첫 YES입니다 ><
D는 휴대폰 자판 하나를 주는데요,(키패드같이 생긴거) 휴대폰 자판 누르는 순서가 정해졌을 때, 손가락에 잉크를 바르고 휴대폰 자판 위로 손가락을 옮겨가며 자취를 만들었을 때, 그 자취를 최소개수의 line segment로 표현해보는 것이 문제입니다.(excellent, good, bad 구분 있는데 별 의미는 없습니다 :) )
D는 가능한 모든 직선을 고려하는 방법으로 풀 수 있습니다. 즉 모든 기울기를 고려해보는거죠.. 가능한게 얼마 안되는데 가로선, 세로선, (delta 가로, delta 세로) = (+-1, +-2), (+-2, +-1), (+-1, +-3)인 것들만 세보면 됩니다.
이 때 주의할 점이 하나 있는데, 다른 모든 직선은 여러 line segment가 있으면 하나의 움직임으로 처리할 수 있는 반면(1-2, 2-3은 1-3 한 번으로 되죵~) 2-5, 8-0 하나만 딱 예외입니다. 이 경우를 예외로 처리해서 잘 세면 됩니다.
대회 초반 시간을 약 15분 잡아먹었던 근성의 코드는 다음과 그다지 다르지 않았습니다. 솔직히 한 번에 Yes 나온게 신기하네요 ++ 읽어주셔서 감사합니다 :)
~~~ c++
int count(int *arr, int n) {
int i, ret(0);
int path[10][10];
memset(path, 0, sizeof(path));
for(i = 1; i < n; ++ i) {
path[arr[i - 1]][arr[i]] = path[arr[i]][arr[i - 1]] = 1;
}
if(path[1][2] || path[2][3] || path[1][3]) ++ ret;
if(path[4][5] || path[5][6] || path[4][6]) ++ ret;
if(path[7][8] || path[8][9] || path[7][9]) ++ ret;
if(path[1][4] || path[4][7] || path[1][7]) ++ ret;
if(path[3][6] || path[6][9] || path[3][9]) ++ ret;
if(path[5][8] || path[2][8] || path[5][0] || path[2][0]) {
++ ret;
}
else {
if(path[2][5]) ++ ret;
if(path[8][0]) ++ ret;
}
if(path[7][0]) ++ ret;
if(path[4][8]) ++ ret;
if(path[1][5] || path[5][9] || path[1][9]) ++ ret;
if(path[2][6]) ++ ret;
if(path[9][0]) ++ ret;
if(path[6][8]) ++ ret;
if(path[3][5] || path[5][7] || path[3][7]) ++ ret;
if(path[2][4]) ++ ret;
if(path[1][6]) ++ ret;
if(path[4][9]) ++ ret;
if(path[3][4]) ++ ret;
if(path[6][7]) ++ ret;
if(path[1][8]) ++ ret;
if(path[4][0]) ++ ret;
if(path[2][9]) ++ ret;
if(path[3][8]) ++ ret;
if(path[6][0]) ++ ret;
if(path[2][7]) ++ ret;
if(path[1][0]) ++ ret;
if(path[3][0]) ++ ret;
return ret;
}
~~~