문제https://www.acmicpc.net/problem/1328설명접근 방법만 잘 찾으면 어렵지 않은 문제라고 생각한다. 개인적으로 bottom-up 접근법보다 top-down 접근법으로 생각하는 것이 도움이 되었다. 물론 후술할 풀이는 bottom-up으로 접근하던 top-down으로 접근하던 충분히 떠올릴 수 있는 풀이이다. 단, 높이가 N인 빌딩보다 1인 빌딩을 움직이는 것이 도움이 될 것이다.N개의 빌딩이 랜덤하게 배치되었다고 가정하자. 왼쪽에서 봤을 때 빌딩의 수를 L, 오른쪽에서 봤을 때 빌딩의 수를 R이라고 하자. 이제 높이가 1인 빌딩을 제외하자. N은 N - 1이 될 것이며, L, R은 높이가 1인 빌딩에 기존에 어디에 있었는지에 따라 달라진다.높이가 1인 빌딩이 가장 왼쪽에 위치했..

문제https://www.acmicpc.net/problem/1103설명 전형적인 그래프 탐색 문제이지만, 사이클이 발생한 경우를 탐지해야 하므로 BFS 대신 DFS를 사용하는 것이 효율적이다. 그러나 단순히 DFS를 수행하며 동전이 움직일 수 있는 최대 횟수를 구하려고 하면 시간 초과가 발생하게 된다. 이미 방문한 지점인 경우, 추가적인 탐색을 진행하면 안 된다. 따라서 DP 배열을 추가로 선언해야 한다.코드더보기#include #include using namespace std;int ans = 0;bool cycleFlag = false;int n, m;int board[50][50];int visited[50][50];int cnt[50][50];int dx[4] = { -1,0,1,0 };int..

문제https://www.acmicpc.net/problem/5015설명 단순히 문자열 관련 알고리즘을 사용해야하는 줄 알았는데, DP와 재귀를 사용하는 문제였다. 패턴 pattern과 문자열 s를 입력받고 pattern의 pidx번 째 인덱스와 s의 sidx번 째 인덱스끼리의 문자열을 비교해서 매칭된다면 1, 아니면 0을 리턴하는 함수 solve()를 선언하였다.코드더보기#include #include using namespace std;int dp[101][101];string pattern;string s;// dp의 초기값을 -1로 설정void init() { for (int i = 0; i = pattern.length()) return 0; // 현재 패턴의 문자가 *가 아닌데 s가 끝난 경..

문제https://www.acmicpc.net/problem/1621설명 원숭이가 N개의 바나나를 가져간다. 두 가지 선택지가 있는데, 바나나 하나만 가져가거나 K개를 한꺼번에 가져가는 방법이 있다. 하나만 가져가는 경우 바나의 무게만큼 시간이 걸리며 K개를 한꺼번에 가져가면 C의 시간이 걸린다. 원숭이가 바나나를 모두 옮기는 데 걸리는 최소 시간과 한꺼번에 옮기는 행위의 횟수, K개 묶음의 왼쪽 위치를 오름차순으로 출력해야 한다. 답이 여러 개인 경우 한꺼번에 옮기는 행위가 최소가 되는 상황을 선택해야 한다.  N개의 바나나를 옮기는 데 최소 시간을 구해야 하므로 DP를 사용한다. 또한 K개 묶음의 왼쪽 위치를 출력해야 하므로 이를 역추적하는 배열(route) 또한 추가로 필요하다.  dp 배열은 현재..

문제https://www.acmicpc.net/problem/2533설명DFS로 트리를 순회하며 가능한 얼리 어답터의 수를 구하는 문제이다. 최소 얼리 어답터의 수를 구하기 위해 DP를 사용한다. 먼저 노드 연결 관계를 vector 배열 nodes에 저장한다. DFS로 순회하며 DP 배열을 초기화한다. 사용할 DP 배열은 이차원 배열이다. dp[i][j]는 i번 째 노드가 얼리 어답터(j == 1) 또는 얼리 어답터가 아닐 때(j == 0) 가능한 최소 얼리 어답터의 수이다. 현재 참조하는 노드를 node, 자식 노드를 child라고 할 때 child의 DFS 순회를 마치고 node에 대한 DP배열을 초기화한다. node가 얼리 어답터가 아닐 때 자식 노드는 무조건 얼리 어답터여야 한다. 즉, dp[no..

문제https://www.acmicpc.net/problem/1509설명처음부터 끝까지 문자열을 순회하면서 팰린드롬을 찾고, 계속하여 최솟값을 갱신해야 한다. dp[i]를 i번 째 문자까지의 최소 분할 횟수라고 하자. 현재, 문자열의 i번 째 인덱스를 가리킨다고 할 때, i번 째 문자를 마지막으로 하는 팰린드롬이 있는지 확인한다. 만약 문자열 처음부터 팰린드롬이라면 최소 분할 횟수 minCuts를 1로 설정한다. 만약 j번 째 문자부터 i번 째 문자까지 팰린드롬이라면 분할 횟수는 dp[j - 1] + 1이다. 물론 이 경우가 최적이 아닐 수 있기 때문에 minCuts과 dp[j - 1] + 1 중 작은 값을 취해야 할 것이다.코드더보기#include #include #include using namesp..

문제https://www.acmicpc.net/problem/1562설명비트필드를 통한 DP를 통해 해결하였다. 3차원 DP 배열을 선언한 후, 길이가 1인 경우에 대하여 초기화를 진행했다. n이 100 이하이고, 비트필드의 최댓값은 1023이므로 삼중 for문을 통해 충분히 해결 가능하다. for문을 순회하며 값이 존재하는 경우 계단 수의 마지막 수와 1씩 차이나는 새로운 계단 수의 경우에 대해 DP 배열을 초기화하였다. 만약 비트필드의 값이 1023이라면 모든 숫자를 방문한 것이다.코드더보기#include using namespace std;unsigned long long dp[101][10][1 > n; for (int i = 1; i = 0) dp[i][j - 1][k | (1