https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net n개 이전의 값들의 금액 최댓값을 구하다 보면 메모이제이션으로 n개의 카드를 구매하는 금액의 최댓값을 구할 수 있다. #include #include #define num 1002 using namespace std; int n, p[num], dp[num]; void input(){ cin >> n; for(int i=1; i> p[i]; } void solution(){ dp[0] = p[0] = 0..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net n일 동안 일을 하는데, 백준이가 얻을 수 있는 최대 수익은 얼마인지 구하는 프로그램을 작성하면 된다. 완전 탐색과 dp 중 하나를 선택하면 된다. n이 15 이하이므로 완전 탐색도 가능하다. 근데, dp 연습을 하고 싶어서 dp로 해봤다. 규칙 찾는게 생각보다 어려웠다.. 하나의 예시를 잡고 막일(..)을 하면 나름 잘 보이는데 뭔가 너무 꼬아서 생각해서 오히려 독이 되었다. 흑흑 1일부터 n일까지 각 날짜까지만 일을 한다면 구할 수 있는 최대 수익을 구하고 dp배열에 넣고 모두 구하면 max value를 구하면 된다. dp는 이전..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 오르막 수 : 수의 자리가 오름차순을 이루는 수 → 인접한 수가 같아도 오름차순으로 친다. 수는 0으로 시작 가능 수의 길이 n이 주어졌을 때, 오르막 수의 개수 구하기(10,007로 나눈 나머지 출력) 길이 1 -> 0, 1, 2, 3,..., 9 = 총 10개 길이 2 -> 00, 01, ... , 11, 12, 13,..., 99 = 총 55개 길이 n -..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 요약 1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 2. 연속된 세 개의 계단을 모두 밟아서는 안된다. 3. 시작점은 계단에 포함되지 않는다. 4. 마지막 도착 계단은 반드시 밟는다. 1번째 밟고 2번째 혹은 3번째 계단 오를 수 있다. 1번째 밟고 4번째 혹은 2-3번째 계단을 연속으로 모두 밟을 수 없다. 이 게임에서 얻을 수 있는 총점수의 최댓값 구하기 범위 계단의 개수 N (1 ..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 요약 N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오. 여기서 fibonacci(1)이 호출되면 1, fibonacci(0)이 호출되면 0을 출력한다. fibonacci(i)의 0과 1의 값을 차례대로 더해서 fibonacci(N)의 0과 1의 값을 출력하면 된다. [0의 개수, 1의 개수] fib(0) : [1, 0] fib(1) : [0, 1] fib(2) : [1, 1] fib(3) : [1, 2] fib(4)..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 요약 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하라. (1 ≤ n ≤ 1,000) 출력 형태 방법의 수를 10007로 나눈 나머지를 출력한다. 문제를 보면 주어진 n에 대해서 2xn 타일링 경우의 수를 구하는 것이다. 이를 작은 문제를 분해해보자. 2xi 타일을 채울 수 있는 방법의 수를 구해서 점점 값을 올려 2xn을 타일로 채울 수 있는 경우의 수를 구할 수 있을 것 같다. i =..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 요약 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하자. 문제를 읽어보면 짧은 문제인데, 막상 풀려고 하면 막막해진다. 우선 규칙을 찾아보도록 해보자. 문제는 주어진 n에 대해서 n을 1, 2, 3의 합으로 표현되는 경우의 수를 구하는 것인데, 작은 문제들을 먼저 해결하는 방식으로 생각해보면 i(≤n)를 1, 2, 3의 합으로 표현할 수 있는 경우의 수들을 찾으면 간단하게 풀 수 있을 것 같다. X를 1, 2, 3의 합으로 표현하려면 그 전의 값(X-1)에 +1만 하면 X가 된..