[SWEA] 2819. 격자판의 숫자 이어 붙이기 -DP

이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB&categoryId=AV7I5fgqEogDFAXB&categoryType=CODE

사실 다 풀고 나서다른 분들이 풀고 블로그에 올린 풀이들을 봤는데....

거의 다 DFS로 접근하시더라고요....

풀고 나서 보니까 '아 그러게 DFS로 생각하기 딱 좋네...' 싶네요 ㅋㅋㅋㅋ

그리고 거의 STL에 있는 set을 많이 사용하셨는데 저는 그걸 몰라서...ㅠㅠㅋㅋㅋㅋ

좀 다른 방식으로 접근 했습니다!

먼저 몇개를 만들 수 있냐는 질문에

처음으로 들었던 생각은 6칸씩 움직이면서 모든 수를 만들어보고, 각 수가 만들어진 여부를 vector <bool> 에 저장한 후에

각 수가 아직 안 만들어졌으면 카운트를 하고, 이미 안 만들어져있다면 카운트를 안해야겠다.

그리고 cache를 이용해서 같은 수를 가지고 같은 위치에 같은 이동 횟수만큼 남았다면 중복 계산하는걸 막아야겠다.

싶었습니다. 나름 DP인거죠.

그게 이 cache입니다

제 ADT는

이렇습니다

우선 각 칸에서 이동할 수 있는 칸이 정해져 있으니 매번 새로 계산하지 말고 한번 계산해서 nextPos에 저장합니다.

pos를 2차원으로 표현하지 않고 1차원으로 표현해서 매개변수의 수를 줄이고 싶었습니다.

아래 함수는 처음에 nextPos를 초기화하는 함수입니다.

0000000~9999999 각 수가 만들어진 여부를 bool isMade에 저장합니다. 당연히 초기값은 false이겠죠?

countNum은 그 상황에서 몇 개의 새로운 수를 반환할 수 있는지로 했습니다.

countNum을 재귀호출해서 steps==0일때

isMade[num]값이 false면 true로 바꾸고 1을 반환하고,

true면 0을 반환하기로 했습니다.

재귀 호출 할때에는 steps-1를 넣고, num은 한칸민 다음에 현재 board에 있는 수를 더해야겠죠.

그래서 num*10(한칸 밀고) + board[nextPos[pos][i]] (현재 board에 있는 수) 로 작성했습니다

제 main함수 입니다. 

http://colorscripter.com/s/Qy98ZRw