모나오랭의 개발일지

https://www.acmicpc.net/problem/30621  다이나믹 프로그래밍(DP)를 사용하여 문제를 풀어주면 됩니다. 시간 배열이 1차원이므로 형태가 복잡하진 않습니다. 문제의 DP 규칙은 다음과 같습니다. 1. dp[i] = dp[i - 1] -> i번째 시간에 '어'를 외칠 수 없는 경우2. dp[i] = confuse[i] -> i번째의 혼란이 이전 최종 혼란보다 큰 경우3. dp[i] = dp[index] + confuse[i] -> i번째 시간에 '어'를 외칠 수 있는 경우 3번째 규칙을 판단하려면 이전 dp값들 중 가장 큰 누적 혼란을 가진 index를 찾아야 하는데, 선형 탐색은 시간 복잡도가 크므로 이분 탐색(binary search)을 사용해줍니다. dp[index]보다 c..

https://www.acmicpc.net/problem/20303  유니온 파인드(Union-Find)와 다이내믹 프로그래밍(DP)을 이용하는 것이 큰 틀입니다. 처음에 DP를 사용하지 않고 문제를 풀어갔는데, 친구 그룹이 꼭 하나란 보장이 없기에 DP를 사용해야 되는 것을 깨달았습니다.. (ex. K = 8, 각각 3명, 4명씩 친구인 그룹의 총 사탕 합이 최대일 수 있음) 1. 아이들이 가지는 사탕 개수 배열, 유니온 파인드의 부모 배열, 루트를 중심으로 그룹에 속한 아이들의 수를 저장하는 사이즈 배열, 최대 사탕 수를 저장하는 dp 배열을 생성합니다. 2. 친구 관계를 입력받을 때마다 유니온 파인드를 통해 아이들의 관계를 정리합니다. 이때 하위 그룹을 귀속할 때 상위 그룹의 루트에 하위 그룹의 사..

https://www.acmicpc.net/problem/17404   문제와 흡사하게 다이나믹 프로그래밍(DP)을 사용하는 문제입니다.근접한 집들끼린 같은 색으로 칠하지 않아야 하는데, 추가로 처음 집과 마지막 집의 색도 달라야 합니다. 처음에 문제를 풀 때 첫번째 집의 색의 정보를 저장한 배열을 따로 만들어 DP를 실행할 때마다 새로 저장을 했습니다.  너무 복잡하고 연산이 뜻대로 되지 않았습니다. 다시 문제를 풀 때 dp[n - 1][i]의 처음 집 색을 구하고 n번째 집의 색을 다른 두 가지 중 cost가 낮은 색을 택하려고 했습니다. 하지만 처음 시도와 달리 첫 집의 색을 저장하지 않아 답이 안 나왔습니다. 그래서 처음부터 집 색을 하나 정하고, 그다음에 DP를 진행하여 마지막 집의 색을 처음 ..

https://www.acmicpc.net/problem/17626  문제를 잘 읽어야 하는 게, 처음에 자연수 4개 이하로 합을 표현할 수 있다는 점을 보지 않고 혼자 "7개 8개 이상으로 숫자가 많으면 경우의 수가 너무 많은데 어떻게 표현하지?" 생각하며 끙끙댔습니다. 그러고 문제를 다시 보니 4개 이하로 표현한다는 부분을 읽었습니다...ㅎㅎㅎ 문제는 DP를 이용해 풀면 됩니다.  1. 인덱스에 해당하는 숫자가 몇 개로 표현이 가능한 지 개수를 저장하는 배열 dp[50001]을 생성합니다. 2. dp[0] = 0, dp[1] = 1 로 dp 배열을 초기화합니다. (0은 경우의 수가 없고, 1은 1*1 로 표현 가능) 3. 제곱수인 경우를 비교합니다. 즉 dp[i + j]의 값을 구할 때 j가 제곱수인..

https://www.acmicpc.net/problem/2579  DP를 통해 문제를 풀어나갑니다. 그러기 위해선 규칙을 찾아야 하는데, 늘 DP 문제는 규칙을 찾는게 일인 것 같습니다.연속으로 2번까지만 오를 수 있고, 두 칸을 오르는 것은 언제든 가능합니다. 그럼 n번째 계단까지 올랐을 때의 점수는 다음 두 가지가 나옵니다. 1. stair[n] + stair[n - 1] + stair[n - 3] : 계단을 연속으로 오르는 경우, i - 3번째 계단을 더하는 이유는 연속으로 한 칸 씩 올랐다는 점을 구분짓기 위함! 2. star[n] + stait[n - 2] : 계단을 두 칸 오르는 경우 위의 규칙을 이용하여 DP 방식으로 문제를 풀어나가면 됩니다.  #include int n;int stair..

https://www.acmicpc.net/problem/1932  배낭 문제와 원리가 같은 다이나믹 프로그래밍(DP) 문제입니다. 최댓값을 구하는게 그나마 다른 점...?밑으로 진행할 수록 경우의 수가 하나씩 증가하는데, N번째 줄에서 연산하는 인덱스가 N - 1 을 넘지 않으므로 따로 초기화할 필요 없이 N * N 크기의 배열을 이용하면 됩니다.  1. 문제에서 입력받는 숫자들을 저장하는 2차원 배열과 합의 경우의 수를 줄마다 저장하는 2차원 배열 dp[][] 를 생성합니다. 2. 경우의 수를 저장하는 2차원 배열에 합을 저장할 건데, 이 때 저장하는 방법으로 이전 줄의 왼쪽과 오른쪽 숫자 중 그동안 누적 합이 더 큰 부분을 고른 후 현재 줄의 숫자를 더합니다. 다시 말해 더 큰 숫자를 고르는 것이 ..