1. 가장 긴 바이토닉 부분 수열
1) 문제
문제 설명
수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.
수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)출력
첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <vector> #include <iostream> #include <algorithm> using namespace std; int N; int main() { cin >> N; vector<int> seq; vector<int> dp1(N,1); vector<int> dp2(N,1); for (int i=0; i<N; i++) { int temp; cin >> temp; seq.push_back(temp); } dp1[0] = 1; dp2[0] = 1; for (int i = 1; i<N; i++) { for (int j = 0; j < i; j++) { if (seq[j] >= seq[i]) continue; dp1[i] = max(dp1[j] + 1, dp1[i]); } } seq = vector<int>(seq.rbegin(), seq.rend()); for (int i = 1; i<N; i++) { for (int j = 0; j < i; j++) { if (seq[j] >= seq[i]) continue; dp2[i] = max(dp2[j] + 1, dp2[i]); } } dp2 = vector<int>(dp2.rbegin(), dp2.rend()); int answer = 0; for (int i=0; i<N; i++) { answer = max({dp1[i] + dp2[i], answer}); } cout << answer-1; }
2. 행렬 곱셈 순서
1) 문제
문제 설명
크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.
AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.
같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.
입력
첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)
항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.
출력
첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <vector> #include <iostream> #include <algorithm> #include <climits> using namespace std; int N; int answer=INT_MAX; int main() { cin >> N; // 0: row, 1:col vector<pair<int, int>> mats; // dp[i][j] : i to j 까지의 최소 비용 vector<vector<int>> dp(N+1, vector<int>(N+1, INT_MAX)); mats.push_back({}); for (int i=1; i<=N; i++) { int row,col; cin >> row >> col; mats.push_back({row, col}); dp[i][i] = 0; } // 길이가 len인(포함된 원소가 len+1개인) 슬라이딩 윈도우를 이동. // start와 end로 표현하고 이 사이에 원소가 len+1개 있음. for (int len = 1; len < N; len++) { for (int start = 1; start + len <= N; start++) { int end = start + len; // start to end의 최솟값을 계산 for (int k=start; k < end; k++) { // (start to k) + (k+1 to end) + (start row * k+1 row * end col) dp[start][end] = min(dp[start][k]+ dp[k+1][end] + (mats[start].first * mats[k+1].first * mats[end].second), dp[start][end]); } } } cout << dp[1][N] << '\n'; }
3. 무한 수열
1) 문제
문제 설명
무한 수열 A는 다음과 같다.
N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.입력
첫째 줄에 3개의 정수 N, P, Q가 주어진다.출력
첫째 줄에 AN을 출력한다.
제한
0 ≤ N ≤
2 ≤ P, Q ≤
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <vector> #include <iostream> #include <unordered_map> #include <algorithm> using namespace std; long long N ; int P,Q; unordered_map<long long, long long> cache; long long dfs(long long num) { if (cache.find(num) != cache.end()) return cache[num]; return cache[num] = dfs(num/P) + dfs(num/Q); } int main() { cin >> N >> P >> Q; cache[0] = 1; cache[1] = 2; long long res = dfs(N); cout << res << '\n'; }
4. 합분해
1) 문제
문제 설명
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
입력
첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.출력
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <vector> #include <iostream> #include <algorithm> using namespace std; #define MOD 1000000000 int N,K; // (K,N) K개 사용해서 N개 만드는 경우의 수 vector<vector<long long>> dp; int main() { cin >> N >> K; dp.resize(K+1, vector<long long>(N+1)); for (int i=1; i<=N; i++) { dp[1][i] = 1; } for (int i=1; i<=K; i++) { dp[i][1] = i; } // cnt개의 숫자를 사용 for (int cnt = 2; cnt<=K; cnt++) { // cnt개 사용해서 i를 만들고 싶은 상황 for (int i = 2; i<=N ; i++) { dp[cnt][i] = dp[cnt-1][i] + dp[cnt][i-1]; dp[cnt][i] %= MOD; } } cout << dp[K][N] << '\n'; }
5. 평범한 배낭
1) 문제
문제 설명
이 문제는 아주 평범한 배낭에 관한 문제이다.한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
입력
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.입력으로 주어지는 모든 수는 정수이다.
출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
제한
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <vector> #include <iostream> #include <algorithm> using namespace std; int N,K; int W,V; vector<pair<int,int>> wvPair; vector<vector<int>> dp; int main() { cin >> N >> K; dp.resize(N+1, vector<int>(K+1)); for (int i=0; i<N; i++) { cin >> W >> V; wvPair.push_back({W,V}); } //DP[index][maxweight] maxweight까지 사용가능한 상황에서, index번째 물건까지 고려했을떄 //가능한 최대 가치 for (int index=1; index<N+1; index++) { for (int maxweight=1; maxweight<K+1; maxweight++) { // 현재 남은 무게가 넣으려고 하는 물건의 무게보다 크면 // (공간이 남으면) if (maxweight - wvPair[index - 1].first >= 0) { // 안 넣은 경우, 넣은 경우 비교해서 큰 거 저장 dp[index][maxweight] = max(dp[index-1][maxweight], dp[index - 1][maxweight - wvPair[index - 1].first] + wvPair[index - 1].second); } else { dp[index][maxweight] = dp[index-1][maxweight]; } } } cout << dp[N][K] << '\n'; }
