키베이루's diary

1) 문제설명 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 2) 아이디어 DP를 2중 배열로 선언한 뒤 숫자를 제거했을 때와 제거하지 않았을 때를 따로 저장한다. DP [0][X] : 숫자를 제거하지 않은 연속합 DP [1][X] : 숫자를 하나 제거한 연속합 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int d..

1) 문제설명 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 2) 아이디어 전에 풀었던 쉬운 계단 수와 비슷한 문제이다. https://kiveiru.tistory.com/16?category=557953 [C++] 백준 10844번 쉬운 계단 수 1) 문제설명 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈..

1) 문제설명 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 2) 아이디어 처음에는 2차원 배열로 dp를 설정하여 마릿수 / n층으로 표를 그려 규칙을 찾으려고 했으나 규칙을 찾기가 매우 어려웠다. 따라서 이를 해결하기 위해 dp [n층][사자를 배치하지 않음/ 사자를 왼쪽에 배치/ 사자를 오른쪽에 배치]로 나누어서 생각하였다. 처음 dp [1][0] = 1층에 사자를 배치하지 않는 경우의 수는 = 1이다 마찬가지로 dp [1][1] = 1층에 사자를 왼쪽 배치할 경우의 수 = dp [1][2] = 1층에 사자를 오른쪽 배치할 경우의 수 = 1 이후 2층에 사자를 배치할 경우..

1) 문제설명 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 2) 아이디어 1을 만들기 위해 필요한 1,2,3의 값은 dp [1] = 1 (1) 2를 만들기 위해 필요한 1,2,3의 값은 dp [2] = 2 (1+1) (2) 3을 만들기 위해 필요한 1,2,3의 값은 dp [3] = 4 (1+1+1) (1+2) (2+1) (3) 이때 4를 만들기 위해 필요한 1,2,3의 값을 살펴보면 1+1+1+1 -> (1+1+1 +1) 1+2+1 -> (1+2 +1) 2+1+1-> (2+1 +1) 3+1 ..

1) 문제설명 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 2) 아이디어 표를 그리면서 생각하였다. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 입력받은 배열(표)에서 먼저 누적합을 구한다. sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + arr[i][j] - sum[i - 1][j - 1]; // 누적합 1 3 6 10 3 8 15 24 6 15 27 4..

1) 문제설명 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 2) 아이디어 DP문제를 1부터 차근차근 시도하다가 끝부분에서 Ti가 N을 넘어버리면 안 되기 때문에 구현에 어려움을 느꼈다. 또한 상담에 걸리는 일수에 따라 최댓값이 바뀌는 것에 대한 점화식도 생각해야 했다. 그래서 반대로 끝에서부터 차근차근 생각하였다. 문제에 있는 표를 끝에서 부터 살펴보면 DP [7] = 0 -> Ti 가 2기 때문에 범위(N)를 넘어가 버린다. DP [6] = 0 -> Ti 가 4기 때문에 범위(N)를 넘어가 버린다. DP [5] = 15 -> Ti가 범위를 넘어가지 않는다. DP [4] = 2..

1) 문제설명 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 2) 아이디어 DP문제는 1부터 차근차근 생각해야 한다. DP [N] : 카드를 N개 갖기 위해 지불해야 하는 금액의 최대로 설정한다. DP [1] = 카드를 1개 갖기 위해 지불해야 하는 최대 금액 = arr [1] * 1 DP [2] = 카드를 2개 갖기 위해 지불해야 하는 최대 금액 = arr [2] * 1 or arr [1] * 2 = dp[0] + arr[2] or dp[1] + ..

1) 문제설명 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 2) 아이디어 DP문제는 항상 기준을 정해두고 생각해야 한다. 이번 문제 같은 경우 DP [X원이 될 수 있는] = 경우의 수로 놓고 생각하였다. 순차적으로 생각해보면 DP [1] : 1원이 될수있는 경우의 수는 1원짜리 하나로 만들수있기때문에 DP[1] = 1이 된다. DP [2] : 2원이 될수있는 경우의 수는 1원짜리 2개 | 2원짜리 1개로 만들 수 있다. DP[2] = 2 D..