DP (2) 썸네일형 리스트형 백준 2565 전깃줄 - 아이디어가 중요한 DP 문제 문제 링크 www.acmicpc.net/problem/2565 풀이 아이디어 아이디어가 되게재밌다. 우선 전기줄이 '겹치게 되는는' 조건이 어떻게 되는지를 한번 생각해 봐야된다. 왼쪽 전봇대에서 위 아래로 시작하는 줄이 오른쪽 전봇대에서 아래 위로 끝나면 겹치게 된다. 근데 이렇게 생각하기 시작하면 개인적으로 좀 어려워 진다고 생각한다. 하나 기준을 정해야 한다. 왼쪽 전봇대로 정하는 것이 편하다. sort가 편하기 때문이다. 그러면 왼쪽 기준으로 정렬 되어있는 상태에서 for문을 돌릴 때, 오른쪽 에서 대소관계의 순서가 유지되면 안겹치는 것이다. 문제의 그림을 예시로 들자면 A를 기준으로 오름차순 정렬을 한 후 탐색을 진행하는 것이다. 1,2에서 시작하는 전기줄은 각각 8,2에서 끝난다. 1,2를 볼 .. 백준 1261 알고스팟: bfs와 caching 쓰는 문제 c++ https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 사실 이 문제는 분류가 다익스트라 알고리즘으로 분류되어있었는데, 그 알고리즘에 대해서 몰라도 풀수 있다. 전형적인 bfs문제는 아니고 다이나믹 프로그래밍의 캐시 개념만 조금 쓰면 풀 수 있다. 어떻게 보면 최단 경로 문제이기 때문에 (빙빙 돌아가면서 벽을 부숴가면서 미로를 탐색하진 않을것 아닌가?) bfs를 쓰는 것은 당연한 .. 이전 1 다음
