답은 알고리즘 뿐이야!

문제 출처 : https://www.acmicpc.net/problem/2449 문제 풀이 : DP 문제입니다. cache[L][R] : L번째 전구부터 R번째 전구까지 통일 시키는데 색을 바꾼 최소횟수 양쪽 구간의 색을 통일 시킬때 변수를 하나 두시고 양쪽 구간의 시작 색깔이 같다면 바꾸는 비용을 0으로, 다르다면 바꾸는 비용을 1로 계산하여 쌓아가시면 됩니다.

문제 출처 : https://www.acmicpc.net/problem/2342 문제 풀이 : DP문제입니다. cache[idx][l][r] : idx번째 지시사항이고 왼발이 l번째칸 오른발이 r번째 칸에 있을때의 사용된 최소힘 이라고 두고 cache를 쌓으시면 됩니다. 칸별로 이동시 드는 힘은 dir[5][5] 배열을 선언하여 편하게 처리하도록 합시다.

문제 출처 : https://www.acmicpc.net/problem/1103 풀이 : DFS 문제입니다. BFS로 풀게되면 이전에 온 경로를 알 수 없으므로 DFS를 사용하여 풀어야 합니다. DFS로 현재까지 온 경로를 체크하면서 오면 중복해서 가는 지점을 찾을 수 있어 무한대로 움직이는 경우를 찾을 수 있습니다. 그리고 시간 단축을 위해 메모이제이션 개념을 사용해 그 지점에 도착했을때 현재 이동한 횟수가 이전에 그 지점에 도달했을때의 횟수보다 작다면 스킵해줍니다. 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 #include int n, m, ret, visit[50][50], cache[5..