본문 바로가기
728x90
반응형

전체 글77

[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.
728x90
반응형

티스토리툴바