https://www.acmicpc.net/problem/11054
풀이: b[i] = i 위치 왼쪽에 있는 값들 중 m[i] 보다 작은 수들의 최대 갯수
s[i] = i 위치 오른쪽에 있는 값들 중 m[i] 보다 작은 수들의 최대 갯수
가장 긴 수열의 길이 = 모든 i 에 대해 (b[i] + s[i] + 1) 의 최댓값
코드: 사용언어 : c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <iostream>#include <algorithm>using namespace std; int n, m[1001], b[1001], s[1001], ma = 0; int main() { cin >> n; for (int i = 0; i < n; i++) cin >> m[i]; for (int i = n - 2; i >= 0; i--) for (int t = n - 1; t > i; t--) if (m[i] > m[t]) s[i] = max(s[i], s[t] + 1); for (int i = 0; i < n; i++) { for (int t = 0; t < i; t++) if (m[i] > m[t]) b[i] = max(b[i], b[t] + 1); ma = max(ma, b[i] + s[i] + 1); } cout << ma << endl; return 0; }
https://www.acmicpc.net/problem/12865
풀이: DP[i] : i 무게일 때, 배낭에 넣을 수 있는 물건의 가치의 최댓값
DP[i + w] = max(DP[i + w], DP[i] + v)
무게가 i + w 일 때, 최댓값은 이전에 있었던 i + w 일때의 값과, i 에 있는 값에 w 무게 물건의 가치인 v를 더한 값 중 최댓값이다.
(DP를 DP[2][100001] 처럼 두개로 나누어 놓은 이유는 물건의 갯수가 1개씩이기 때문에 물건 중복을 피하기위해 나누어놓았다.)
ex) 무게가 4이고, 가치가 5일때, DP[4] = 5 가 되지만, DP[8] = DP[4] + 5 가 되어 10이 되는 불상사가 일어날 수 있기 때문에, 두개로 나누어 놓앗다.
https://www.acmicpc.net/problem/14888
풀이: 각 숫자를 순서대로 배열에 넣어놓는다.
+, -, *, / 를 갯수만큼 각 숫자사이의 끼워넣어 식을 만든다.
만들 식의 값들을 배열에 저장해놓는다.
배열에 들어있는 수 중 최댓값, 최솟값을 출력한다.
코드: 사용언어 : c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include <iostream>#include <vector>#include <algorithm>using namespace std; int n, num[101], op[4]; vector<int> sumn; void o(int a, int b) { if (a == n - 1) { sumn.
https://www.acmicpc.net/problem/14889
풀이: n / 2 명의 스타트 팀과 n / 2 팀의 링크팀을 만든다.
스타트팀만 만든다면, 자동적으로 남는 사람들은 링크팀이된다.
구하는 팀에 1은 무조건 들어가도록한다. (1을 포함한 팀을 전부 구한다면, 1을 포함하지 않는 팀은 상대팀에 모두 있기 때문에)
스타트팀의 모든 Sij 값의 합과 링크팀의 모든 Sij 값의 합의 차이를 구한다.
구한 차이들 중 가장 작은 값을 출력한다.
코드: 사용언어 : c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include <iostream>#include <algorithm>using namespace std; int n, m[21][21], mn = 100000, start, link; bool s[21]; void st(int a, int b) { if (a == n / 2) { start = 0; link = 0; for (int i = 0; i < n; i++) if (s[i]) { for (int t = i + 1; t < n; t++) if (s[t]) start += m[i][t] + m[t][i]; } else for (int t = i + 1; t < n; t++) if (!
https://www.acmicpc.net/problem/1676
풀이: 뒤에서 0이 나오려면 팩토리얼을 곱할때, 5 가 곱해져야한다.
즉, 5의 배수가 지나간다면, 팩토리얼의 갯수가 1씩 늘어날 것이다.
팩토리얼을 만드는 동안 5가 몇번 곱해지는지 계산한다면, 0의 갯수를 구할 수 있다.
(이 문제는 N의 제한이 500 까지이기 때문에, 팩토리얼을 전체 계산해서 구하기는 힘들다.)
코드: 사용언어 : c++
1 2 3 4 5 6 7 8 9 10 11 12 13 #include <iostream>using namespace std; int main() { int n, m = 0; cin >> n; while (n) { n /= 5; m += n; } cout << m << endl; return 0; }
