๐ฃ ๋ฌธ์ ์ดํด
์์ด A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} ์ธ ๊ฒฝ์ฐ ํฉ์ด ๊ฐ์ฅ ํฐ ์ฆ๊ฐ ๋ถ๋ถ ์์ด์
A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} ์ด๊ณ , ํฉ์ 113์ด๋ค.
๋์ ๊ณํ๋ฒ(Dynamic Programming) ๋ฐฉ์์ ์ฌ์ฉํ๋ค.
๐ญ ํ์ด ๊ณผ์
์์ ๋ฌธ์ 11053๋ฒ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด ๊ณผ ๊ฑฐ์ ์ ์ฌํ๋ค.
๋์ ๊ณํ๋ฒ ํ์ด
์์ฑ ์ธ์ด: C++
#include <cstdio>
int biggestIncreasingSeq (int arr[][1010], int size) {
int sumMax = 0, l_result = 0;
for (int i = 0; i < size; ++i) {
for (int j = 0; j < i; ++j) {
if (arr[0][i] > arr[0][j]) {
sumMax = arr[1][j] > sumMax ? arr[1][j] : sumMax;
}
}
arr[1][i] = sumMax + arr[0][i];
if (arr[1][i] > l_result) {
l_result = arr[1][i];
}
sumMax = 0;
}
return l_result;
}
int main() {
int seqArr[2][1010] = {0,};
int numCnt = 0, result = 0;
scanf("%d", &numCnt);
for (int i = 0; i < numCnt; ++i) {
scanf("%d", &seqArr[0][i]);
}
result = biggestIncreasingSeq(seqArr, numCnt);
printf("%d\n", result);
return 0;
}
์ด๋ฒ์๋ ์์ ๊ฐ์๋ฅผ ๊ธฐ๋กํ๋ ๊ฒ์ด ์๋ ์์ ํฉ์ ๊ธฐ๋กํ๊ณ , ๋งค๋ฒ ์ต๋ ํฉ์ ๊ฐฑ์ ํ๋ค.
sumMax: 0, result: 1
1 | 100 | 2 | 50 | 60 | 3 | 5 | 6 | 7 | 8 |
1 |
์ฒซ ๋ฒ์งธ ์๋ ์๊ธฐ ์์ ๋ฐ์ ์์ผ๋ฏ๋ก ๋ถ๋ถ์์ด ํฉ์ด 1 ์ด๋ค.
์ง๊ธ๊น์ง ๊ฐ์ฅ ํฐ ์ฆ๊ฐ ๋ถ๋ถ์์ด์ ํฉ์ 1 ์ด๋ค.
sumMax: 1, result: 101
1 | 100 | 2 | 50 | 60 | 3 | 5 | 6 | 7 | 8 |
1 | 101 |
๋ ๋ฒ์งธ ์๋ ๋ํ ์ ์๋ ์ ์ค ๊ฐ์ฅ ํฉ์ด ํฐ ๊ฒ์ด 1 ์ด๋ฏ๋ก ๋ถ๋ถ์์ด ํฉ์ด 101 ์ด๋ค.
์ง๊ธ๊น์ง ๊ฐ์ฅ ํฐ ์ฆ๊ฐ ๋ถ๋ถ์์ด์ ํฉ์ 101 ์ด๋ค.
sumMax: 1, result: 101
1 | 100 | 2 | 50 | 60 | 3 | 5 | 6 | 7 | 8 |
1 | 101 | 3 |
์ธ ๋ฒ์งธ ์๋ ๋ํ ์ ์๋ ์ ์ค ๊ฐ์ฅ ํฉ์ด ํฐ ๊ฒ์ด 1 ์ด๋ฏ๋ก ๋ถ๋ถ์์ด ํฉ์ด 3 ์ด๋ค.
์ง๊ธ๊น์ง ๊ฐ์ฅ ํฐ ์ฆ๊ฐ ๋ถ๋ถ์์ด์ ํฉ์ 101 ์ด๋ค.
sumMax: 3, result: 101
1 | 100 | 2 | 50 | 60 | 3 | 5 | 6 | 7 | 8 |
1 | 101 | 3 | 53 |
๋ค ๋ฒ์งธ ์๋ ๋ํ ์ ์๋ ์ ์ค ๊ฐ์ฅ ํฉ์ด ํฐ ๊ฒ์ด 3 ์ด๋ฏ๋ก ๋ถ๋ถ์์ด ํฉ์ด 53 ์ด๋ค.
์ง๊ธ๊น์ง ๊ฐ์ฅ ํฐ ์ฆ๊ฐ ๋ถ๋ถ์์ด์ ํฉ์ 101 ์ด๋ค.
sumMax: 53, result: 113
1 | 100 | 2 | 50 | 60 | 3 | 5 | 6 | 7 | 8 |
1 | 101 | 3 | 53 | 113 |
๋ค์ฏ ๋ฒ์งธ ์๋ ๋ํ ์ ์๋ ์ ์ค ๊ฐ์ฅ ํฉ์ด ํฐ ๊ฒ์ด 53 ์ด๋ฏ๋ก ๋ถ๋ถ์์ด ํฉ์ด 113 ์ด๋ค.
์ง๊ธ๊น์ง ๊ฐ์ฅ ํฐ ์ฆ๊ฐ ๋ถ๋ถ์์ด์ ํฉ์ 113 ์ด๋ค.
sumMax: 3, result: 113
1 | 100 | 2 | 50 | 60 | 3 | 5 | 6 | 7 | 8 |
1 | 101 | 3 | 53 | 113 | 6 |
์ฌ์ฏ ๋ฒ์งธ ์๋ ๋ํ ์ ์๋ ์ ์ค ๊ฐ์ฅ ํฉ์ด ํฐ ๊ฒ์ด 3 ์ด๋ฏ๋ก ๋ถ๋ถ์์ด ํฉ์ด 6 ์ด๋ค.
์ง๊ธ๊น์ง ๊ฐ์ฅ ํฐ ์ฆ๊ฐ ๋ถ๋ถ์์ด์ ํฉ์ 113 ์ด๋ค.
sumMax: 6, result: 113
1 | 100 | 2 | 50 | 60 | 3 | 5 | 6 | 7 | 8 |
1 | 101 | 3 | 53 | 113 | 6 | 11 |
์ผ๊ณฑ ๋ฒ์งธ ์๋ ๋ํ ์ ์๋ ์ ์ค ๊ฐ์ฅ ํฉ์ด ํฐ ๊ฒ์ด 6 ์ด๋ฏ๋ก ๋ถ๋ถ์์ด ํฉ์ด 11 ์ด๋ค.
์ง๊ธ๊น์ง ๊ฐ์ฅ ํฐ ์ฆ๊ฐ ๋ถ๋ถ์์ด์ ํฉ์ 113 ์ด๋ค.
sumMax: 11, result: 113
1 | 100 | 2 | 50 | 60 | 3 | 5 | 6 | 7 | 8 |
1 | 101 | 3 | 53 | 113 | 6 | 11 | 17 |
์ฌ๋ ๋ฒ์งธ ์๋ ๋ํ ์ ์๋ ์ ์ค ๊ฐ์ฅ ํฉ์ด ํฐ ๊ฒ์ด 11 ์ด๋ฏ๋ก ๋ถ๋ถ์์ด ํฉ์ด 17 ์ด๋ค.
์ง๊ธ๊น์ง ๊ฐ์ฅ ํฐ ์ฆ๊ฐ ๋ถ๋ถ์์ด์ ํฉ์ 113 ์ด๋ค.
sumMax: 17, result: 113
1 | 100 | 2 | 50 | 60 | 3 | 5 | 6 | 7 | 8 |
1 | 101 | 3 | 53 | 113 | 6 | 11 | 17 | 24 |
์ํ ๋ฒ์งธ ์๋ ๋ํ ์ ์๋ ์ ์ค ๊ฐ์ฅ ํฉ์ด ํฐ ๊ฒ์ด 17 ์ด๋ฏ๋ก ๋ถ๋ถ์์ด ํฉ์ด 24 ์ด๋ค.
์ง๊ธ๊น์ง ๊ฐ์ฅ ํฐ ์ฆ๊ฐ ๋ถ๋ถ์์ด์ ํฉ์ 113 ์ด๋ค.
sumMax: 24, result: 113
1 | 100 | 2 | 50 | 60 | 3 | 5 | 6 | 7 | 8 |
1 | 101 | 3 | 53 | 113 | 6 | 11 | 17 | 24 |
์ด ๋ฒ์งธ ์๋ ๋ํ ์ ์๋ ์ ์ค ๊ฐ์ฅ ํฉ์ด ํฐ ๊ฒ์ด 24 ์ด๋ฏ๋ก ๋ถ๋ถ์์ด ํฉ์ด 32 ์ด๋ค.
์ง๊ธ๊น์ง ๊ฐ์ฅ ํฐ ์ฆ๊ฐ ๋ถ๋ถ์์ด์ ํฉ์ 113 ์ด๋ค.
๊ฐ์ฅ ํฐ ์ฆ๊ฐ ๋ถ๋ถ์์ด ํฉ์ 113 ์ด ๋๋ค.
๐ ๋ฐฐ์ด ์
์ญ์ ๋น์ทํ ์ ํ์ ์ ํ๋ฉฐ ์ฝ๊ฒ ํด๊ฒฐํ ๋ฌธ์ ์ด๋ค.
๋ง์ด ํ์ด๋ณด๋ ๊ฒ์ด ํ์ด๋ผ๋ ๊ฒ์ ์ค๊ฐํ๊ฒ ๋๋ค.