BOJ 14462 소가 길을 건너간 이유 8
https://www.acmicpc.net/problem/14462 14462번: 소가 길을 건너간 이유 8 존 (우리가 지금까지 도와 주었던 존과는 다른 인물이다)의 농장에는 N 종류의 소가 있다. 각각 1번 종, 2번 종, ..., N번 종 (1 ≤ N ≤ 1000)이다. 만약 |a−b| ≤ 4라면 a번 종과 b번 종의 소는 친하지만 www.acmicpc.net 왼쪽의 i 번째 소, 오른쪽의 j 번째 소를 이을려고 할 때 (물론 두 소가 친한 경우에) 어떻게 해야할 까 생각해보니, DP로 풀면 되겠다고 생각했다. 왜냐하면, i 번째 소, j 번째 소를 이을 때, [ 0,0 ] ~ [ i - 1, j - 1 ] 조합 중 가장 많은 소를 연결하는 경우에 더해 i , j 를 잇기만 하면 되기 때문에, DP..
BOJ 14451 안대 낀 스피드러너
https://www.acmicpc.net/problem/14451 14451번: 안대 낀 스피드러너 "전진, 우회전, 전진, 전진, 좌회전, 전진, 좌회전, 전진, 전진"의 순서를 따르면 6초 또는 9초만에 도착할 수 있다. www.acmicpc.net 딱 보고 떠오르는 풀이가 없어 차근차근 생각하기로 했다. 처음 생각한 풀이는 naive 하게 경로의 경우의 수를 완전탐색하여 푸는 것이였다. 당연히 시간초과라고 생각했고, 그럼 BFS로 탐색하면 어떨까 생각했는데, 2개의 경우(상 방향 출발, 우 방향 출발)를 어떻게 고려할 지 고민을 좀 했다. 생각하던 찰나 그냥 한꺼번에 같이 탐색을 돌리면 어떨까라는 생각을 하게 됬다. 마침 크기도 작아서 n^6 까지 가능한 것을 확인하고, 해당 풀이를 확신했다. 아..