본문 바로가기
728x90
반응형

algorithm56

[algorithm] 백준 - 연속합 2 이 문제는 DP 문제이다. 1. 수는 한 개 이상 선택해야한다. 2. 수열에서 수를 하나 제거할 수 있다. 수를 제거했을 경우, 수를 제거 하지 않았을 경우로 나누어서 계산한다. 만약 수를 제거 했다면, 현재 위치한 수를 합산하지 않는다면, 여태까지 수열 중 제거한 적이 없는 값 합산한다면 제거한 적이 있는 값 을 비교해서 큰 값을 누적한다. dp[i][1] = max(arr[i] + dp[i - 1][1], dp[i - 1][0]); 수를 제거하지 않는다면, 현재 위치한 수와 수열 중 제거한 적이 없는 값을 비교해서 큰 값을 누적한다. dp[i][0] = max(arr[i] + dp[i - 1][0], arr[i]); 따라서 이런 식으로 코드를 작성했다. // 연속합(2) #include using n.. 2020. 11. 3.
[algorithm] 백준 - 가장 긴 증가하는 부분 수열 1 & 4 DP 문제이다. 순서대로 반복문을 돌다가 증가하는 부분을 확인하면서 값을 올리는 방식으로 풀면 된다. // 가장 긴 증가하는 부분수열 4 #include #include using namespace std; int main(void){ int count, answer = 1, dp[1001], arr[1001]; stack stack; cin >> count; for(int i = 0; i > arr[i]; dp[i] = 1; for(int j = 0; j arr[j] && dp[i] 2020. 11. 3.
[algorithm] 백준 - 스티커 DP 문제이다. 점수가 매겨진 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 점수에 합산될 수 없다. 스티커는 2*N으로 배치되어있다. 예를 들어 이런 스티커가 있다고 가정해보자. 50 10 100 20 40 30 50 70 10 60 이런 방향과 이런 방향으로 합산을 할 수 있다. 즉 대각선방향 값과 대각선방향으로 앞에 첫번째 쪽 값의 합산 중 가장 큰 것을 비교해서 계산하면 된다. 두번째 세번째 앞의 값은 계산할 필요가 없다. 그 이유는 이런 식으로 계산이 되기 때문이다. 그렇기 때문에 대각선 방향에 위치한 값, 대각선 방향의 인덱스 - 1 에 위치한 값 중 큰 것으로 선택하면 된다. 점수를 차례차례 합산하여 최댓값을 계산해보면, 50 40 200 140 250 30 100 120 210 260.. 2020. 11. 2.
[algorithm] 백준 - 오르막수 DP 문제이다. 문제의 포인트는 0부터 시작할 수 있다는 것과 오름차순 수열, 그리고 인접한 수가 같아도 된다는 것이다. 자릿수가 1일 때, 0 1개 1 1개 2 1개 ... 9 1개 로 10개이고, 자릿수가 2일 때, 수열의 마지막 수 다음에 올 수 있는 수 0 0,1,2,3...9 1 1,2,3,4...9 2 2,3,4,5...9 ... ... 9 9 총 55개 라는 것이다. 그럼 수열의 마지막 수를 j라 하고 올 수 있는 수를 k라 했을 때, j에서 k만큼의 경우의 수를 더한다는 것을 알 수 있다. 코드로 표현해보면 이렇다. // 오르막수 #include using namespace std; int main(void){ int count, total = 0,dp[1001][10] = {0}; cin.. 2020. 11. 2.
[algorithm] 백준 - 쉬운 계단 수 DP 문제이다. 이 문제의 특징은 모든 자리수의 차이가 1이 난다는 것이다. 그렇다면, 마지막 자릿수 다음 자릿수 0 1 1 0, 2 2 1, 3 ... ... 9 8 로 이루어질 수 있다. n을 자릿수라고 생각했을 때, n = 2 일 때, 12 10 21 23 ... 98 n = 3 일 때, 121 120 101 210 212 232 234 ... 989 987 이것을 점화식으로 표현해보면, dp[n][i] = dp[n - 1][i - 1] + dp[n - 1][i + 1] 로 계속 쌓아나가는 과정을 볼 수 있다. 코드로는 // 쉬운 계단 수 #include using namespace std; int main(void){ long long count, dp[101][10], total = 0; cin.. 2020. 11. 2.
[algorithm] 백준 - 1,2,3 더하기 5 DP문제이다. n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 것이다. 여기서 중요한 점은 같은 수를 두 번 이상 연속해서 사용하면 안된다는 것이다. 그렇기에 뒷자리수를 함께 기록해야한다. 뒷자리수가 1일 때 다음 수는 2나 3이, 2이면 다음 수는 1이나 3, 3이면 다음 수는 1이나 2 여야한다. 이것을 점화식으로 표현해보자면, dp[i][1] = dp[i - 1][2] + dp[i - 1][3]; dp[i][2] = dp[i - 2][1] + dp[i -2][3]; dp[i][3] = dp[i - 3][1] + dp[i - 3][2]; 전체 코드는 이렇다. // 1, 2, 3 더하기 5 #include using namespace std; int main(void){ long long te.. 2020. 11. 2.
728x90
반응형

티스토리툴바