-

https://www.acmicpc.net/problem/2011 > s; dp[0] = 1; for (int i = 1; i = 1 && x

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net DP 연습문제다. DP[자리수][끝수]라고 정했을 때 맨 윗줄 DP[1][0] ~ DP[1][9]는 모두 1로 선언해준다. 그 다음, DP[N][K] = DP[N-1][0] + DP[N-1][1] + ... + DP[N-1][K]와 같이 점화식을 구성해주면..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 백준 DP 연습문제다. 끝 자리에 유의해서 DP[자리수][끝자리수]로 만들 수 있는 계단수를 찾으면 된다. 수가 매우 커지기 때문에 모듈러 연산을 위해 long long에 정답을 저장해야 하며, 동작과정 중 n을 만나면 계산해둔 값을 이용해 답을 출력한뒤 종료하도록 구현했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include #pragma warning(..

https://www.acmicpc.net/problem/4811 4811번: 알약 문제 70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다. 첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다. 다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다 www.acmicpc.net 백준 4811번 알약 문제다. DP 유형의 문제로 생각할 수 있다. DP[W][H]라고 하는 배열이 온전한 알약이 W개, 반쪽짜리 알약이 H..

https://www.acmicpc.net/problem/5557 5557번: 1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. www.acmicpc.net 전형적인 DP 문제였습니다. 배열의 성격을 잘 결정하고, 초기값을 잘 결정해준 뒤 점화식을 세워 코딩하면 되는 문제입니다. dp[i][j]를..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되 www.acmicpc.net 백준 DP 연습문제다. 행이 1~N, 열이 0, 1로 이루어진 표를 그려 문제를 풀었다. 행은 길이를, 열은 0또는 1로 끝나는 해당 길이..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 1과 2, 3을 활용해 어떤 수의 합으로 표현하는 방법을 구하는 문제다. 예를 들어 4를 만들고자 할 때 어떻게 하면 될까? ..