Problem_Solving/DP
-
[SWEA] 9092. 마라톤Problem_Solving/DP 2020. 1. 3. 17:00
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW7Opy-KWPoDFAWY& DP와 찰떡궁합인 문제. DP를 적용하면 너무나 예쁘게 풀립니다. http://colorscripter.com/s/SqvPRIB https://github.com/rundun159/PS/blob/master/Problem_Solving/9092.cpp (제가 구현한 코드입니다.) 제 코드에서 핵심이 되는 matrix는 graph와 cache입니다. 먼저, graph라는 2D array에 각 지점들 사이의 L1거리를 저장합니다. (연산횟수를 줄이기 위함입니다. ..
-
[SWEA] 1247. 최적 경로 -DPProblem_Solving/DP 2019. 2. 3. 19:38
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD&categoryId=AV15OZ4qAPICFAYD&categoryType=CODE 문제를 읽고 짧은 시간 안에 해결해야 하는 문제인줄 알고 겁부터 먹었지만 모든 가능한 경로를 살펴서 해를 찾아도 좋다기에 신나는 마음으로 완전 탐색을 적용할 생각을 했습니다. ㅎㅎ 문제 형태를 보아하니 주로 쓸 함수를 이렇게 정의하면 좋을것 같더라고요. ㅎㅎ visited에는 현재까지 방문한 고객들을 비트마스크를 이용해서 표현하고, last는 마지막으로 방문한 고객의 index를 ..
-
[SWEA] 2819. 격자판의 숫자 이어 붙이기 -DPProblem_Solving/DP 2019. 2. 2. 16:43
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB&categoryId=AV7I5fgqEogDFAXB&categoryType=CODE 사실 다 풀고 나서다른 분들이 풀고 블로그에 올린 풀이들을 봤는데.... 거의 다 DFS로 접근하시더라고요.... 풀고 나서 보니까 '아 그러게 DFS로 생각하기 딱 좋네...' 싶네요 ㅋㅋㅋㅋ 그리고 거의 STL에 있는 set을 많이 사용하셨는데 저는 그걸 몰라서...ㅠㅠㅋㅋㅋㅋ 좀 다른 방식으로 접근 했습니다! 먼저 몇개를 만들 수 있냐는 질문에 처음으로 들었던 생각은 6칸씩 ..