https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 1. Logic dp배열의 의미 : 해당 좌표를 통해 먹을 수 있는 대나무의 최대 갯수 2. Code #include using namespace std; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; int n; int bamboo[501][501]; bool vis[501][501]; int dp[501][501]; int dfs(i..
TOPDOWN
https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 1. Logic 먼저 DP테이블이 의미하는 것은 n초에 먹을 수 있는 자두의 최대 갯수이다. dp[자두떨어지는 시간][움직인횟수][위치한나무번호] 부분문제를 쪼개보자면 시작할때는 1. 1번 나무에서 시작하는 경우 2. 2번 나무에서 시작하는 경우 이후에는 1-1. 1번나무에서 받아먹고 계속 1번에 있는 경우 1-2. 1번나무에서 받아먹고 2번나무로 옮기는 경우 2. 2번나무에서 받아먹고 계속 2번에 있는 ..
https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 1. Logic 처음에 이 문제를 딱 보고 위상정렬인줄 알았다. 하지만 위상정렬의 탈을 쓴 DP문제였고 결국 멘토한테 도움을 받았다. 내가 처음에 짠 코드는 동시에 진행하는 작업 중에 가장 시간이 오래 걸리는 작업의 시간이 고려되지 않을 수도 있는 코드였다. 그래서 이 문제는 위상정렬과 코드가 비슷하긴 하지만 DP로 풀이해야 한다. 2. Code #include using namespac..
https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 1. Logic 동일한 경로의 비행기 노선이 있을 수 있기 때문에 기내식의 점수가 가장 높은 것 만을 입력받아줬다. 그리고 DP배열이 의미하는 바는 당연 가장 높은 기내식 점수이다. dp[도시의 번호][몇번째로 방문한 도시인지] 2. Code #include #include #include #include using namespace ..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1. Logic 부분문제를 3가지로 나눌 수 있다. 포도주를 안마시는 경우 포도주를 1잔 연속해서 마시느 경우 포도주를 2잔 연속해서 마시는 경우 그래서 DP테이블을 정할 때 DP[현재 인덱스][선택 여부] 로 정의했다. 선택 여부 별 의미하는 바는 > 0:이전에 포도주 안마심, 1:이전에 한잔만 마심, 2:이전에 두잔 연속해서 마심 입력으로 받은 첫번째 수에서 선택할지 말지여부를 처리하는 것은, ..
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 1. Logic 펠린드롬을 확인 할 때 문자를 뒤집어서 봤을 때 똑같으면 펠린드롬인데 이렇게 구현해버리면 시간복잡도가 2000 * 1000000 == 약 20억 정도 나오기 때문에 제한 시간 안에 풀지 못한다. 그래서 나는 재귀를 통해서 인덱스를 +1 -1씩 해주었고 펠린드롬이면 dp[start][end]에 1을 아니면 0을 넣어서 메모이제이션 해줬다. 2. Code #include using namespace std; int dp[2..
