문제링크 : https://www.acmicpc.net/problem/12026 12026번: BOJ 거리 스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; char arr[1001]; int dp[1001]; bool check(char cur, char next) //BOJ 순서 확인 { if(cur=='B' && next == 'O') return 1; if(cur=='O' && next == 'J') retu..
문제링크 : https://www.acmicpc.net/problem/13325 13325번: 이진 트리 입력 데이터는 표준입력을 사용한다. 입력의 첫째 줄에는 포화이진트리의 높이를 나타내는 양의 정수 k(1 ≤ k ≤ 20)가 주어진다. 두 번째 줄에는 모든 에지들의 가중치가 주어진다. 에지들의 가 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int k, tsize, result; int arr[1> k; tsize = 1 갭 x : return 1+2 = 3 11 -> 갭 x : return 1+4 = 5 35 -> 갭 2 : return 2+5..
문제링크 : https://www.acmicpc.net/problem/11568 11568번: 민균이의 계략 민균이는 요즘 준민이를 놀리는 일에 재미가 들렸다. 오늘도 그는 준민이를 놀리기 위해 한가지 재미있는 아이디어를 떠올렸다. 그는 하나의 정수가 쓰여 있는 카드 N장을 준비하여 준민이에게 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, result; int arr[1001], dp[1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i=0; i>..
문제링크 : https://www.acmicpc.net/problem/1695 1695번: 팰린드롬 만들기 앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; int arr[5001]; int dp[5001][5001]; int func(int s, int e) { if(s>=e) return 0; /..
문제링크 : 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)..