https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net DP문제 DP[N][L] : N 자리 수에 L 이 올 경우, 오르막 수 조건에 해당하는 경우의 수 ex) DP[3][5] -> _ _ 5 (3번째 자리의 5가 올경우) 점화식: DP[N][L] = DP[N-1][0] + DP[N-1][1] + ... + D..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 문제조건 DP 문제 현재 마실 수 있는 포도주를 wine[i], 현재가 최대일 경우를 저장해놓은 배열을 dp[i]라고 하자. 연속으로..
https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 0은 2와 5의 의해 계산된다. (10 = 2x5) 5의 배수는 2의 배수보다 항상 적으므로 n보다 작은 5의 배수에서 5가 몇번 곱해져있는지 계산하면 된다. 시간을 줄이기 위해, n을 5의 제곱수만큼 나눠주면 5가 총 몇번 들어있는지 바로 알 수 있다. ex) 100/5 = 20 (5의 배수가 총 20번) 100/25 = 4 (25의 배수가 총 4번) => 20+4 = 24 #include using namespace std; int main(){ ios_base::sync_wit..
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 정수 X에 사용할 수 있는 연산 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. DP 문제 1. 3으로 나눌 때 dp[n] = dp[n/3] + 1 2. 2로 나눌 떄 dp[n] = dp[n/2] + 1 3. 1을 뺄 때 dp[n] = dp[n-1] + 1 => n일 때 가장 작은 방법 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); ci..
https://www.acmicpc.net/problem/1149 1149번: RGB거리 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net DP문제!! i 번째까지 칠했을 때 최소 가격 = (i-1) 번째까지 칠한 가격 + i 칠한 가격 => d[i] = d[i-1] + i번째 최솟값 으로 생각할 수 있다. 하지만!! 이전을 R로 ..
