Hello Ocean! 🌼

문제 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 풀이 저번에 풀었던 내리막길 문제와 비슷하게, DFS+DP 를 이용하면 풀 수 있는 문제였다. bba-dda.tistory.com/entry/%EB%B0%B1%EC%A4%80C-1520-%EB%82%B4%EB%A6%AC%EB%A7%89-%EA%B8%B8 [백준/C++] 1520. 내리막 길 문제 www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를..

문제 www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 시작정점부터, 다른 모든 정점까지의 최단경로를 구하는 단순한(?) 문제이다. 풀이 다익스트라 알고리즘을 이용하였다. #include #include #include using namespace std; #define INF 987654321 int min_route[20002]; int V, E, start; vector adj[20002]; void DijkstraHeap() ..

문제 programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 구해보자! 제한사항 이 마을에 있는 집은 3개 이상 1,000,0..

문제 www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 DP로 풀면 된다! cache[i]: i를 짓는데 까지 걸리는 시간 i를 짓는데 걸리는 시간을 찾는 함수에서, 1) cache값이 있으면 바로 return 2) 없으면, 새로 구해서 cache에 채워넣고 return 한다 i를 짓는데 걸리는 시간 = i 건설 시간 + max( i전에 지어야 하는 건물들의 건설 시간 ) 코드 #include #include #include using namespa..

문제 www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 유의사항 1+2 와 2+1을 다른 경우로 센다는 것. 0도 사용할 수 있다는 것. 경우의 수를 1000000000으로 나눈 나머지를 출력해야한다는 것 풀이 이 문제는 DP(동적 계획법)을 이용하면 풀 수 있다! 2차원 캐시배열을 이용한 메모이제이션을 적용해야 한다. cache[k][n] : k개의 숫자를 더해서 n을 만들 수 있는 경우의 수 그리고 cache[k][n]은 다음과 같이 구할 수 있다. (점화식) cache[k][n] = cache[k-1][0] + cache[k-1][1] + cacke[k-1][2] + ... + c..

문제 www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 처음에는, DP를 어떻게 이용해야할지 떠오르지 않아서 일단 완전탐색으로 구현해보았다. 결과는 너무 당연하게도 시간초과였다! 완전탐색으로 구현하고 나면, DP에 대한 감이 올거라고 생각했는데 전혀 오지 않았다. 결국 검색의 힘을 빌렸는데, 이 문제는 대표적인 "냅색 문제"라고 한다. 냅색 문제(knapsack problem)란? 냅색 문..