'Algorithm/Problem Solving'에 해당되는 글 41건
- 2020.04.20 :: [BOJ/1699] 제곱수의 합
- 2020.04.20 :: [BOJ/2579] 계단 오르기
- 2020.04.19 :: [BOJ/1912] 연속합
- 2020.04.19 :: [BOJ/11054] 가장 긴 바이토닉 부분 수열
- 2020.04.18 :: [BOJ/11722] 가장 긴 감소하는 부분 수열
- 2020.04.18 :: [BOJ/11055] 가장 큰 증가 부분 수열
- 2020.04.17 :: [BOJ/11053] 가장 긴 증가하는 부분 수열
- 2020.04.17 :: [BOJ/2156] 포도주 시식
- 2020.04.16 :: [BOJ/9465] 스티커
- 2020.04.16 :: [BOJ/11057] 오르막 수
(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)
문제 링크
- https://www.acmicpc.net/problem/1699
사용 알고리즘
- DP
풀이
- d[i] = i를 제곱수의 합으로 나타냈을 때, 필요한 항의 최소 개수
- d[i] = min(d[i - (j * j)] + 1) (1 <= i <= j * j)
소스 코드
- https://github.com/moomini/algorithm/blob/master/boj/1699.cpp
|
#include <cstdio>
int d[100003]; int a[100003];
int main(void) { int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { for (int j = 1; j * j <= i; ++j) { if (d[i] == 0) { d[i] = d[i - (j * j)] + 1; } else { if (d[i] > d[i - (j * j)] + 1) d[i] = d[i - (j * j)] + 1; } } } printf("%d\n", d[n]); return 0; } |
'Algorithm > Problem Solving' 카테고리의 다른 글
| [BOJ/9461] 파도반 수열 (0) | 2020.04.22 |
|---|---|
| [BOJ/2133] 타일 채우기 (0) | 2020.04.22 |
| [BOJ/2579] 계단 오르기 (0) | 2020.04.20 |
| [BOJ/1912] 연속합 (0) | 2020.04.19 |
| [BOJ/11054] 가장 긴 바이토닉 부분 수열 (0) | 2020.04.19 |
(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)
문제 링크
- https://www.acmicpc.net/problem/2579
사용 알고리즘
- DP
풀이
- d[i] = i번째 계단에 올라갔을 때의 최대 점수
- d[i] = max(d[i - 2] + a[i], d[i - 3] + a[i - 1] + a[i])
→ 1개 연속 : i - 2번째 계단은 밟고, i - 1번째 계단은 밟지 않아야 됨
→ 2개 연속 : i - 3번째 계단은 밟고, i - 2번째 계단은 밟지 않고, i - 1번째 계단은 밟아야 됨
소스 코드
- https://github.com/moomini/algorithm/blob/master/boj/2579.cpp
|
#include <cstdio>
#include <algorithm>
using namespace std;
int d[303];
int a[303];
int main(void) {
int n; scanf("%d", &n);
int ans = -1;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
if (i == 1) d[i] = a[i];
else if (i == 2) d[i] = a[i] + a[i - 1];
else d[i] = max(d[i - 2] + a[i], d[i - 3] + a[i - 1] + a[i]);
}
printf("%d\n", d[n]);
return 0;
}
|
'Algorithm > Problem Solving' 카테고리의 다른 글
| [BOJ/2133] 타일 채우기 (0) | 2020.04.22 |
|---|---|
| [BOJ/1699] 제곱수의 합 (0) | 2020.04.20 |
| [BOJ/1912] 연속합 (0) | 2020.04.19 |
| [BOJ/11054] 가장 긴 바이토닉 부분 수열 (0) | 2020.04.19 |
| [BOJ/11722] 가장 긴 감소하는 부분 수열 (0) | 2020.04.18 |
(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)
문제 링크
- https://www.acmicpc.net/problem/1912
사용 알고리즘
- DP
풀이
- d[i] = a[i]를 가장 마지막으로 하는 가장 큰 연속합
- d[i] = max(d[i - 1] + a[i], a[i])
소스 코드
- https://github.com/moomini/algorithm/blob/master/boj/1912.cpp
|
#include <cstdio>
int d[100003]; int a[100003];
int main(void) { int n; scanf("%d", &n); int ans = -100000003; for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); d[i] = (a[i] > (d[i - 1] + a[i])) ? a[i] : d[i - 1] + a[i]; if (ans < d[i]) ans = d[i]; } printf("%d\n", ans); return 0; } |
'Algorithm > Problem Solving' 카테고리의 다른 글
| [BOJ/1699] 제곱수의 합 (0) | 2020.04.20 |
|---|---|
| [BOJ/2579] 계단 오르기 (0) | 2020.04.20 |
| [BOJ/11054] 가장 긴 바이토닉 부분 수열 (0) | 2020.04.19 |
| [BOJ/11722] 가장 긴 감소하는 부분 수열 (0) | 2020.04.18 |
| [BOJ/11055] 가장 큰 증가 부분 수열 (0) | 2020.04.18 |
(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)
문제 링크
- https://www.acmicpc.net/problem/11054
사용 알고리즘
- DP
풀이
- d1[i] = a[i]를 가장 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
- d2[i] = a[i]를 가장 마지막으로 하는 가장 긴 감소하는 부분 수열의 길이
- d[i] = d1[i] + d2[i] - 1
→ i가 겹치게 되므로 -1 처리
소스 코드
- https://github.com/moomini/algorithm/blob/master/boj/11054.cpp
|
#include <cstdio>
int d1[1003], d2[1003];
int a1[1003], a2[1003];
int main(void) {
int n; scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a1[i]);
a2[n - i - 1] = a1[i];
}
for (int i = 0; i < n; ++i) {
d1[i] = 1;
d2[i] = 1;
for (int j = 0; j < i; ++j) {
if ((a1[i] > a1[j]) && (d1[j] + 1 > d1[i])) d1[i] = d1[j] + 1;
if ((a2[i] > a2[j]) && (d2[j] + 1 > d2[i])) d2[i] = d2[j] + 1;
}
}
int ans = -1;
for (int i = 0; i < n; ++i) {
if (ans < (d1[i] + d2[n - i - 1] - 1)) ans = d1[i] + d2[n - i - 1] - 1;
}
printf("%d\n", ans);
return 0;
}
|
'Algorithm > Problem Solving' 카테고리의 다른 글
| [BOJ/2579] 계단 오르기 (0) | 2020.04.20 |
|---|---|
| [BOJ/1912] 연속합 (0) | 2020.04.19 |
| [BOJ/11722] 가장 긴 감소하는 부분 수열 (0) | 2020.04.18 |
| [BOJ/11055] 가장 큰 증가 부분 수열 (0) | 2020.04.18 |
| [BOJ/11053] 가장 긴 증가하는 부분 수열 (0) | 2020.04.17 |
(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)
문제 링크
- https://www.acmicpc.net/problem/11722
사용 알고리즘
- DP
풀이
- d[i] = a[i]를 가장 마지막으로 하는 가장 긴 감소하는 부분 수열의 길이
- d[i] = max(d[j]) + 1 (j < i, a[j] > a[i])
소스 코드
- https://github.com/moomini/algorithm/blob/master/boj/11722.cpp
|
#include <cstdio>
int d[1003];
int a[1003];
int main(void) {
int n; scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
int ans = -1;
for (int i = 0; i < n; ++i) {
d[i] = 1;
for (int j = 0; j < i; ++j) {
if ((a[i] < a[j]) && (d[j] + 1 > d[i])) d[i] = d[j] + 1;
}
if (ans < d[i]) ans = d[i];
}
printf("%d\n", ans);
return 0;
}
|
'Algorithm > Problem Solving' 카테고리의 다른 글
| [BOJ/1912] 연속합 (0) | 2020.04.19 |
|---|---|
| [BOJ/11054] 가장 긴 바이토닉 부분 수열 (0) | 2020.04.19 |
| [BOJ/11055] 가장 큰 증가 부분 수열 (0) | 2020.04.18 |
| [BOJ/11053] 가장 긴 증가하는 부분 수열 (0) | 2020.04.17 |
| [BOJ/2156] 포도주 시식 (0) | 2020.04.17 |
(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)
문제 링크
- https://www.acmicpc.net/problem/11055
사용 알고리즘
- DP
풀이
- d[i] = a[i]를 가장 마지막으로 하는 가장 큰 증가 부분 수열의 합
- d[i] = max(d[j]) + a[i] (j < i, a[j] < a[i])
소스 코드
- https://github.com/moomini/algorithm/blob/master/boj/11055.cpp
|
#include <cstdio>
int d[1003]; int a[1003];
int main(void) { int n; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); int ans = -1; for (int i = 0; i < n; ++i) { d[i] = a[i]; for (int j = 0; j < i; ++j) { if ((a[j] < a[i]) && (d[j] + a[i] > d[i])) d[i] = d[j] + a[i]; } if (ans < d[i]) ans = d[i]; } printf("%d\n", ans); return 0; } |
'Algorithm > Problem Solving' 카테고리의 다른 글
| [BOJ/11054] 가장 긴 바이토닉 부분 수열 (0) | 2020.04.19 |
|---|---|
| [BOJ/11722] 가장 긴 감소하는 부분 수열 (0) | 2020.04.18 |
| [BOJ/11053] 가장 긴 증가하는 부분 수열 (0) | 2020.04.17 |
| [BOJ/2156] 포도주 시식 (0) | 2020.04.17 |
| [BOJ/9465] 스티커 (0) | 2020.04.16 |
(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)
문제 링크
- https://www.acmicpc.net/problem/11053
사용 알고리즘
- DP
풀이
- d[i] = a[i]를 가장 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
- d[i] = max(d[j]) + 1 (j < i, a[j] < a[i])
소스 코드
- https://github.com/moomini/algorithm/blob/master/boj/11053.cpp
|
#include <cstdio>
int d[1003]; int a[1003];
int main(void) { int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); int ans = 0; for (int i = 1; i <= n; ++i) { d[i] = 1; for (int j = 1; j < i; ++j) { if ((a[j] < a[i]) && (d[j] + 1 > d[i])) d[i] = d[j] + 1; } if (ans < d[i]) ans = d[i]; } printf("%d\n", ans); return 0; } |
'Algorithm > Problem Solving' 카테고리의 다른 글
| [BOJ/11722] 가장 긴 감소하는 부분 수열 (0) | 2020.04.18 |
|---|---|
| [BOJ/11055] 가장 큰 증가 부분 수열 (0) | 2020.04.18 |
| [BOJ/2156] 포도주 시식 (0) | 2020.04.17 |
| [BOJ/9465] 스티커 (0) | 2020.04.16 |
| [BOJ/11057] 오르막 수 (0) | 2020.04.16 |
(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)
문제 링크
- https://www.acmicpc.net/problem/2156
사용 알고리즘
- DP
풀이
- d[i][j] = i번째 포도주까지 마셨을 때의 최대 포도주의 양. i번째 포도주는 j번 연속으로 마심
- d[i][0] = max(d[i - 1][0], d[i - 1][1], d[i - 1][2])
- d[i][1] = d[i - 1][0] + p[i]
- d[i][2] = d[i - 1][1] + p[i]
소스 코드
- https://github.com/moomini/algorithm/blob/master/boj/2156.cpp
|
#include <cstdio>
#include <algorithm>
using namespace std;
int d[10003][3];
int p[10003];
int main(void) {
int n; scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &p[i]);
for (int i = 1; i <= n; ++i) {
d[i][0] = max(d[i - 1][0], max(d[i - 1][1], d[i - 1][2]));
d[i][1] = d[i - 1][0] + p[i];
d[i][2] = d[i - 1][1] + p[i];
}
printf("%d\n", max(d[n][0], max(d[n][1], d[n][2])));
return 0;
}
|
'Algorithm > Problem Solving' 카테고리의 다른 글
| [BOJ/11055] 가장 큰 증가 부분 수열 (0) | 2020.04.18 |
|---|---|
| [BOJ/11053] 가장 긴 증가하는 부분 수열 (0) | 2020.04.17 |
| [BOJ/9465] 스티커 (0) | 2020.04.16 |
| [BOJ/11057] 오르막 수 (0) | 2020.04.16 |
| [BOJ/10844] 쉬운 계단 수 (0) | 2020.04.14 |
(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)
문제 링크
- https://www.acmicpc.net/problem/9465
사용 알고리즘
- DP
풀이
- d[i][j] = 2 * i개의 스티커에서 얻을 수 있는 최대점수, i번째 열에서 뜯는 스티커는 j
- d[i][0] = max(d[i - 1][0], d[i - 1][1], d[i - 1][2]) (j = 0 : 위, 아래 모두 뜯지 않음)
- d[i][1] = max(d[i - 1][0], d[i - 1][2]) + p[i][0] (j = 1 : 위만 뜯음)
- d[i][2] = max(d[i - 1][0], d[i - 1][1]) + p[i][1] (j = 2 : 아래만 뜯음)
소스 코드
- https://github.com/moomini/algorithm/blob/master/boj/9465.cpp
|
#include <cstdio> #include <algorithm>
using namespace std;
int d[100003][3]; int arr[100003][2];
int main(void) { int t; for (scanf("%d", &t); t--;) { int n; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &arr[i][0]); for (int i = 0; i < n; ++i) scanf("%d", &arr[i][1]); d[0][1] = arr[0][0]; d[0][2] = arr[0][1]; for (int i = 1; i < n; ++i) { d[i][0] = max(d[i - 1][0], max(d[i - 1][1], d[i - 1][2])); d[i][1] = max(d[i - 1][0], d[i - 1][2]) + arr[i][0]; d[i][2] = max(d[i - 1][0], d[i - 1][1]) + arr[i][1]; } printf("%d\n", max(d[n - 1][0], max(d[n - 1][1], d[n - 1][2]))); } return 0; } |
'Algorithm > Problem Solving' 카테고리의 다른 글
| [BOJ/11055] 가장 큰 증가 부분 수열 (0) | 2020.04.18 |
|---|---|
| [BOJ/11053] 가장 긴 증가하는 부분 수열 (0) | 2020.04.17 |
| [BOJ/2156] 포도주 시식 (0) | 2020.04.17 |
| [BOJ/11057] 오르막 수 (0) | 2020.04.16 |
| [BOJ/10844] 쉬운 계단 수 (0) | 2020.04.14 |
(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)
문제 링크
- https://www.acmicpc.net/problem/11057
사용 알고리즘
- DP
풀이
- d[i][j] = i자리 오르막 수의 개수, i번째 자리의 수는 j
- d[1][i] = 1
- d[i][j] += d[i - 1][k] (0 <= k <= j)
소스 코드
- https://github.com/moomini/algorithm/blob/master/boj/11057.cpp
|
#include <cstdio>
int d[1003][10];
int main(void) { int n; scanf("%d", &n); for (int i = 0; i <= 9; ++i) d[1][i] = 1; for (int i = 2; i <= n; ++i) { for (int j = 0; j <= 9; ++j) { for (int k = 0; k <= j; ++k) { d[i][j] += d[i - 1][k]; d[i][j] %= 10007; } } } int ans = 0; for (int i = 0; i <= 9; ++i) { ans += d[n][i]; ans %= 10007; } printf("%d\n", ans); return 0; } |
'Algorithm > Problem Solving' 카테고리의 다른 글
| [BOJ/11055] 가장 큰 증가 부분 수열 (0) | 2020.04.18 |
|---|---|
| [BOJ/11053] 가장 긴 증가하는 부분 수열 (0) | 2020.04.17 |
| [BOJ/2156] 포도주 시식 (0) | 2020.04.17 |
| [BOJ/9465] 스티커 (0) | 2020.04.16 |
| [BOJ/10844] 쉬운 계단 수 (0) | 2020.04.14 |