열심히해보겠씁니다

건물의 종류와 짓는 시간이 주어지고, 각 건물은 먼저 특정 건물이 지어지고 난 이후에나 지을 수 있다. 모든 건물 N개를 완성하는데 걸리는 최소 시간을 출력하면 되므로 일단 DP를 염두에 둘 수 있다. 명령을 내리고 일꾼이 이동하는 시간은 걸리지 않으므로 건물을 짓는 시간만 계산할 수 있고 건물마다 번호가 있으므로 간편하게 DP로 저장할 수 있을 것으로 기대한다. 여기서 두 번째 조건이 걸린다. 특정 건물이 지어지고 난 이후에나 지을 수 있는 건물들이 있는데, 여기서 문제에 나오지 않았지만, 여러 개의 건물이 필요한 경우가 있을 수도 있으므로 이런 경우에도 통과할 수 있도록 indegree를 센다. indegree는 자신에게 들어오는 경로의 개수를 의미하는데, 1, 2 번이 지어지고 난 이후 3번을 지을..

자기만 재밌는 게임을 한다고 한다... 직사각형 보드에서 동전이 구멍에 빠지거나 보드 바깥으로 나가지 않는 선에서 게임을 오래 즐기고 싶다고 한다. 최대 몇 번 움직이는지는 손으로 구해보면 쉽다. 보드의 크기는 최대 50x50이고 각 칸에 적혀있는 숫자는 1~9이며 구멍일 수 있다. 몇 가지 점을 빠르게 알 수 있다. 1. 내가 갈 수 있는 칸에 나와 똑같은 숫자가 있으면 무한번 움직일 수 있다. 1-1. 그러므로 무한번이 아닌 경우는 도착하는 숫자가 모두 다르다. 2. 한 번이라도 지나온 칸에 다시 도착한다면 무한번 움직일 수 있다. 2-2. 다시 도착하지 않는다면 반드시 게임은 종료되고, 따라서 그 칸에서 최대한 움직일 수 있는 횟수는 정해져 있다. 즉 무한번 움직일 수 있는지 판단은 두 가지로 할 ..

가장 긴 증가하는 부분 수열 시리즈 중 난이도가 높은 5이다. 일반적인 방법으로 풀 수 없는 제한 조건이 있다. 수열의 크기가 100만이고, 숫자가 -10억부터 10억까지이므로 기존에 2에서 쓰던 방법들은 시간이 너무 오래 걸린다. 배열을 한 번 순회하면서 O(N) 논리적으로 저장하는 방식이 O(logN)이라면 NlogN ~ 2천만 회 정도로 1초 안에 풀이가 가능하다. 사용할 방법은 백트레킹이다. 이름이 어려워 보이지만, 단순히 내가 한 행동을 저장해 놓고 나중에 다시 꺼내보겠다는 얘기이다. 방식은 다음과 같다. 1. 주어진 수열(A)을 순회한다. 2. 가장 긴 부분 수열을 저장하는 수열(B)에 저장한다. 3. 가장 긴 수열이 저장되었다면, 저장한 값이 A에서는 몇 번째인지 백트레킹으로 추적한 후 저장..

최대 1만개의 마을에서 우수 마을을 선정하는 문제이다. 조건은 다음과 같다. 1. 자신을 포함하여 인접마을 중 적어도 하나는 우수마을이어야 한다. 2. 우수마을끼리는 인접할 수 없다. 3. 트리구조로 되어 N개의 마을과 N-1개의 도로가 있다. 목표는 다음과 같다. 1. 인구를 최대로 해야 한다. 인구를 최대로 할 수 있으면서 조건에 맞춰야하므로 경우의 수를 따져서 탐색해봐야한다. BFS로 접근하기 힘든 문제이므로 DFS를 통해 뽑거나 안뽑는 경우를 나눠 탐색한다. 먼저 다행히 트리구조이므로 순환하는 도로는 없다. 트리구조는 어느 node를 시작점으로 잡아도 트리 모양으로 이루어져 있으니 Root를 1로 두고 접근하였다. 먼저 인구 정보를 POP에, 연결된 도로 정보를 vector인 road에 저장한다...

지금보다 많이 먹길 원하는 돼지 판다의 일생을 계산해보자. 문제의 조건은 다음과 같다. 1. 판다는 상하좌우로 움직인다. 2. 지금 칸의 대나무보다 이동하려는 칸의 대나무가 많을 때만! 이동한다. 3. 갈 곳이 없으면 굶어죽는다.(일생이 끝난다.) 4. 크기는 500x500 이며, 대나무의 최대값은 100만보다 같거나 작다. 처음 문제를 접근한 방법은 다음과 같다. 1. BFS 혹은 DFS로 모든 좌표에서 완전탐색을 실시하여 최댓값을 구한다. 완전탐색시에 발생하는 문제는 다음과 같다. 1. 시간 초과 최적화 방식은 다음과 같이 시도했다. 1. 특정 좌표의 상하좌우 중 자기보다 큰 값이 없을 때(국소 최소값)만 탐색을 시작. 2. visited 배열에 탐색하면서 들렀던 곳과 그 일생(ex. 3일)을 기록해..

아주아주 간단한 문제다. 보기에는. 하지만 DFS로 풀기에는 좀 까다롭다. 왜냐하면 Floor 가 100만 층이나 되기 때문에 최악의 경우(S 1 G 1,000,000 U 1 같은) 100만번을 쌩으로 돌릴 수도 있기 때문이다. depth 가 너무 깊어지기 때문에 터지기 쉽상이므로 다른 방식을 생각해본다. 가장 먼저 생각한 것은 동적 계획법(Dynamic programming)이다. 프로그램을 돌리면서 과거보다 결과가 좋지 않은 것은 전부 쳐내버리는 방법인데, 가령 길을 찾을 때, 옛날에 지나갔던 길이라면 내가 어떻게 애를 써도 그 시간보다 과거로 가서 길을 지나갈 순 없다. 특히 그곳이 목적지였다면 나는 과거에 도착한 것을 알기 때문에 목적지를 구태여 빙 돌아서 한 번 더 갈 필요는 없다. DP가 딱 ..

수열의 어디서부터 출발해서 어떤 것을 골라야 가장 긴 증가하는 수열이 될까를 판단해야 한다. 이를 위해 위치별로 시작해보는 일도 필요하고, 해당 위치에서 가장 긴 수열은 무엇인지도 판단해야한다. 1. 정해진 위치에서 가장 긴 수열 2. 최적화 이 문제는 DFS로 접근했다. 예시의 경우로 보면, 10 20 10 30 20 50 의 index를 1, 2, 3, 4, 5, 6 으로 둔다. 그리고 index별로 차례대로 DFS를 수행하여 조건에 맞는 가장 긴 수열을 찾는다. 이 때도 길 찾기와 마찬가지로 분기별로 나뉘어서 수행하며 가장 길게 가는 수열을 찾아야 한다. int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a..