목록알고리즘/DP (15)

키베이루's diary

[C++] 백준 2579번 계단 오르기

1) 문제설명 2) 아이디어 bottom - up 구조의 for문 DP사용 d [0] = 첫 번째 계단 d [1] = 첫 번째 계단 + 두 번째 계단 d [2] = 첫 번째 계단 + 두 번째 계단 or 두번째 계단 + 세 번째 계단 중에 큰 것. d [i] = i-2번째 계단까지의 최대 + i번 계단 or i-3번째 계단까지의 최대 + i-1번째 계단 + i번째 계단. 3) 코드 int main() { int n; int* arr; cin >> n; arr = (int*)malloc(sizeof(int) * n); for (int i = 0; i > arr[i]; } d[0] = arr[0]; // 10 d[1] = arr[0] + arr[1]; d[2] = max(arr[..
알고리즘/DP 2022. 6. 12. 14:08
[C++] 백준 1932번 정수 삼각형

1) 문제설명 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 2) 아이디어 삼각형에서 DP [줄][몇 번째 숫자] = 합의 최대로 설정하고 0으로 초기화한다. 반복문을 2개 돌려서 DP의 최댓값을 체크한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; long long dp[501][501]={0,}; int main() { int n; long long arr[501][501]; c..
알고리즘/DP 2022. 6. 3. 12:46
[C++] 백준 1149번 RGB거리

1) 문제설명 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2) 아이디어 DP를 이중 배열로 선언한다. DP [1][X] 에는 RED를 DP [2][X]에는 GREEN을 DP [3][X]에는 BLUE를 선택했을 경우로 나눈다. DP [1][X]에서는 DP [2][X-1] or DP [3][X-1]에 RED를 더했을 때의 최솟값을 DP [2][X]에서는 DP [3][X-1] or DP [1][X-1]에 GREEN를 더했을..
알고리즘/DP 2022. 6. 3. 06:05
[C++] 백준 2156번 포도주 시식

1) 문제설명 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2) 아이디어 포도잔이 1개, 2개, 3개, 4개일때 될 수 있는 경우의 수를 하나씩 생각했다. 1개일때 : ( _ ) 2개일때 : ( _ ) ( _ ) 3개일때 : ( _ ) ( _ ) _ || ( _ ) _ ( _ ) || _ ( _ ) ( _ ) 4개일때 : ( _ ) ( _ ) _ ( _ ) || ( _ ) _ ( _ ) ( _ ) || _ _ ( _ ) ( _ ) 1개일때와 ..
알고리즘/DP 2022. 6. 2. 11:40
[C++] 백준 10844번 쉬운 계단 수

1) 문제설명 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2) 아이디어 dp를 이중배열로 받아서 (i / j) 의 인덱스를 각각 (자릿수 / 마지막 수) 로 생각한다. 마지막수/ 자릿수 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 1 1 1 1 1 1 2 1 1 2 2 2 2 2 2 2 1 3 1 3 3 4 4 4 4 4 3 2 4 3 4 7 7 8 8 8 7 6 3 마지막 수가 0 일때와 9일때를 제외한 나머지는 dp[자릿수][마지막수] = dp[자릿수-1][마지막수-1] + dp[자릿수-1][마지막수+1] 인 것을 알 수있다. 3) 코드 #..
알고리즘/DP 2022. 6. 2. 09:36
[C++] 백준 1912번 연속합

1) 문제설명 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 2) 해결방법 입력값 : 2 -> 최대 2 2, 1 -> 최대 2+1 =3 2, 1, -4 -> 최대 2+1 =3 2, 1, -4, 3 -> 최대 2+1 =3 or 3 2, 1, -4, 3, 4 -> 최대 3+4 =7 이와 같이 생각했을 때 (지금까지 입력받았던 합중 최댓값) vs (새로 입력받은 숫자) 중 큰 것으로 dp를 설계하면 된다. 3) 코드 #include #include #incl..
알고리즘/DP 2022. 5. 18. 16:23
[C++] 백준 1463번 1로 만들기

1) 문제설명 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 2) 해결방법 문제를 이해하기 위해서 2부터 하나씩 생각해보았다. 2 -> 1 (2로 나누어 떨어진다) 횟수 : 1 3 -> 1 (3으로 나누어 떨어진다) 횟수 : 1 4 -> 2 -> 1 (2로 두 번 나누어 떨어진다) 횟수 : 2 5 -> 4 -> 2 -> 1 (1을 빼고 2로 두번 나누어 떨어진다) 횟수 : 3 6 -> 3 -> 1 or 6 -> 2 -> 1 (2로 나누고 3으로 나눈다 or 3으로 나누고 2로 나눈다) 횟수 : 2 이와 같이 생각하니 (3으로 나눈 것) vs (2로 나눈 것..
알고리즘/DP 2022. 5. 18. 01:57
Prev 1 2 Next