DP(36)
-
[BOJ 9084] 동전
- 문제 요약 동전의 종류가 주어질 때, 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.입력의 첫 줄에는 테스트케이스의 수 T가 주어진다.각 테스트케이스의 첫 번째 줄에는 동전의 가지 수 N(1(같은 동전이 여러 번 주어지는 경우는 없다. 방법의 수는 2^31-1보다 작다.) - 알고리즘 정리 DP[i] (i원을 만들 수 있는 방법의 수)DP[i] = DP[i] + DP[i - (동전의 금액)] - 코드 작성 #includeusing namespace std;#define MAX 10001typedef long long ll;int t,n,m,arr[21],dp[MAX];int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout..
2024.11.18 -
[BOJ 15989] 1, 2, 3 더하기 4
- 문제 요약 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.합을 나타낼 때는 수를 1개 이상 사용해야 하며, 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.(테스트케이스의 수 T가 주어진다. n은 양수이며 10,000보다 작거나 같다.) - 알고리즘 정리 DP 문제입니다. DP[X][a] (정수 X를 만들 때 a로 끝나는 경우의 수) DP[i][1] = DP[i-1][1] DP[i][2] = DP[i-2][1] + DP[i-2][2] DP[i][3] = DP[i-3][1] + DP[i-3][2] + DP[i-3][3] - 코드 작성 #includeusing namespace std;#define MAX 10001int t,n,dp..
2024.11.18 -
[BOJ 2225] 합분해
- 문제 요약 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다. (1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.(1 - 알고리즘 정리 DP 문제입니다. dp[K][N] = X (K개를 더해서 N을 만들 수 있는 경우의 수가 X)dp[K][N] = dp[K-1][0] + dp[K-1][1] + ... + dp[K-1][N] 위와 같이 점화식을 작성하면 문제를 해결할 수 있습니다. - 코드 작성 #includeusing namespace std;#define MAX 201typedef long long ll;l..
2024.11.18 -
[BOJ 2186] 문자판
https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net - 문제 요약 알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이..
2023.05.23 -
[BOJ 11985] 오렌지 출하
https://www.acmicpc.net/problem/11985 11985번: 오렌지 출하 첫째 줄에 오렌지의 개수 N (1 ≤ N ≤ 20,000), 한 상자에 넣을 수 있는 오렌지 개수의 최댓값 M (1 ≤ M ≤ 1,000, M ≤ N), 상자를 포장하는 비용 K (0 ≤ k ≤ 1,000,000,000)가 주어진다. 둘째 줄부터 N개의 www.acmicpc.net 개수 - 문제 요약 Juicy Orange Industry(JOI)는 맛있는 오렌지를 포장해서 출하하는 것이 주된 업무인 회사이다. JOI사에서는 수집한 N개의 오렌지를 상자에 넣어서 출하한다. 먼저, 오렌지는 공장에 있는 컨베이어 벨트 위에 나란히 놓아야 한다. 컨베이어 벨트 위에 놓여져있는 오렌지는 앞에서부터 순서대로 1부터 N까..
2023.05.07 -
[BOJ 2237] 수열 축소
https://www.acmicpc.net/problem/2237 2237번: 수열 축소 N개의 양수로 이루어진 수열 {A[1], A[2], …, A[N]}이 있다. 이 수열에 A[i]에서 A[i+1]을 빼는 축소 연산을 적용하려 한다. 축소 연산은 CON이라는 함수로 나타낼 수 있으며, CON(A, i)를 수행하면 {A[1], A[2], www.acmicpc.net - 문제 요약 N개의 양수로 이루어진 수열 {A[1], A[2], …, A[N]}이 있다. 이 수열에 A[i]에서 A[i+1]을 빼는 축소 연산을 적용하려 한다. 축소 연산은 CON이라는 함수로 나타낼 수 있으며, CON(A, i)를 수행하면 {A[1], A[2], …, A[i-1], A[i] - A[i+1], A[i+2], …, A[N]}..
2023.05.06