문제링크 : https://www.acmicpc.net/problem/15489 15489번: 파스칼 삼각형 첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R) www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int R, C, W, result; int dp[31][31]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> R >> C >> W; for(int i=1; i
문제링크 : https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; int dp[51]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; dp[0]=dp[1]=1; for(int i=2; i
문제링크 : https://www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, a, b, L; int arr[21]; int dp[21][21][21]; //1번문, 2번문, 현재 위치 int func(int a, int b, int index) { if(index==L) r..
문제링크 : https://www.acmicpc.net/problem/8394 8394번: 악수 첫째 줄에 회의에 참석한 사람의 수 n (1 ≤ n ≤ 10,000,000)이 주어진다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; int dp[10000001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; dp[0]=1; dp[1]=2; for(int i=2; i
문제링크 : https://www.acmicpc.net/problem/11062 11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int T, N; int arr[1001]; int dp[1001][1001][2]; //l, r, 차례 int func(int l, int r, int t) //0 근우, 1 명우 { if(dp[l][r][t]!=-..
문제링크 : https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; int a[2001], b[2001]; int dp[2001][2001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); ..
문제링크 : https://www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int T, K; int p[10001], n[1001]; int dp[10001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> ..
문제링크 : https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; ll arr[33][33]; ll dp[33][33][3]; //0 : 가로, 1 : 세로, 2 : 대각선 int main() { ios_base::sync_with_stdio..
문제링크 : https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; ll dp[31][31]; //w(한 조각), h(반 조각) int main() { ios_base::sync_with_stdio(0); cin.tie(0); while(1) { cin >> N; if(!N) brea..
문제링크 : https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int T, W, result; int arr[1001]; int dp[3][31][1001]; //위치, 움직임, 시간 int main() { ios_base::sync_with_stdio(0); cin.tie(0); c..
문제링크 : https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, num; vectorv[501]; int inDegree[501], dp[501], arr[501]; queueq; int main() { ios_base::sync_with_stdio(0)..
문제링크 : https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; int scv[3]; int dp[61][61][61]; int dfs(int x, int y, int z) { //파괴된 scv가 존재하면 해당 scv는 0으로 if(x scv[i]; } cout
문제링크 : https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; int arr[2001]; int dp[2001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i=0;..
문제링크 : https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int M, N; int arr[501][501]; int dp[501][501]; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; int dfs(int y, int ..
문제링크 : https://www.acmicpc.net/problem/9658 9658번: 돌 게임 4 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int dp[1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; dp[1]=0; dp[2]=1; dp[3]=0; dp[4]=1; //1이 상근이가 이기는 경우 for(int i=5; i 1개 가져가면 상대방이 나머지 가져가야 하므로 이김 dp[..