-
[BOJ] 11055 : 가장 큰 증가 부분 수열
11055 : 가장 큰 증가 부분 수열 풀이 d[i] = i번째 수까지의 부분 수열 중 최댓값으로 놓자! d[i] = d[j] + a[i] lis에서 dp 배열에 길이를 넣는 것 대신 최댓값을 넣어주면 된다. 코드 #include <stdio.h> int n, ans, a[1001], d[1001]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); d[i] = a[i]; for (int j = 0; j <= i; j++) { if (a[j] < a[i] &&...
-
[BOJ] 1699 : 제곱수의 합
1699 : 제곱수의 합 풀이 knapsack 풀듯이 똑같이 풀면 된다! 배낭에 무게가 i*i이고 가치가 1인 돌덩이들을 넣는다고 생각하자! dp[j] = min(dp[j-i*i] + 1, dp[j]) 코드 #include <stdio.h> int n, d[100001]; int min(int a, int b) { return a < b ? a : b; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) d[i] = 1e9; for (int i = 1; i*i <= n; i++) for (int j =...
-
[BOJ] 1309 : 동물원
1309 : 동물원 풀이 d1[i] = 2*i인 우리에서 i번째 칸에 사자를 0마리 놓는 경우의 수 d2[i] = 2*i인 우리에서 i번째 칸의 한 쪽에만 사자를 1마리 놓는 경우의 수 d1[i] = d1[i-1] + d2[i-1] * 2 d2[i] = d1[i-1] + d2[i-1] 위의 식을 그대로 써도 좋지만, 1차원으로 더 압축해보자! 위에서 정의한 d1과 d2를 잘 기억하자. d1[i] = d1[i-1] + d2[i-1] * 2 d1[i] = (d1[i-2] + d2[i-2] * 2) + (d1[i-2] + d2[i-2]) * 2 d1[i]...
-
[BOJ] 2133 : 타일 채우기
2133 : 타일 채우기 풀이 타일은 n이 짝수인 경우에만 완벽히 채울 수 있다. 2*1 타일을 맨위와 맨아래에 일렬로 배치하는 경우에 유의하자. dp[i] = dp[i-2] * 3 + dp[i-j] * 2 (4 <= i, 4 <= j <= i) 코드 #include <stdio.h> int main() { int n, d[31] = { 1,0,3 }; scanf("%d", &n); for (int i = 4; i <= n; i += 2) { d[i] = d[i - 2] * 3; for (int j...
-
[BOJ] 1316 : 그룹 단어 체커
1316 : 그룹 단어 체커 풀이 i번째 문자와 i-1번째 문자가 같다면 둘은 연속된 문자이므로 같은 그룹에 속한다. 단어가 그룹에 속해있지 않는 경우는 이미 앞에서 동일한 문자가 나왔고, i번째 문자와 i-1번째 문자가 다른 경우이다. 체킹 배열을 만들어서 체크해주자! 코드 #include <iostream> #include <string> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int tc, ans = 0; string str; cin >> tc; while (tc--) { bool chk[26] = { 0 }, flg = 0; cin >> str;...