๐ฃ ๋ฌธ์ ์ดํด
์์ด A = {10, 20, 10, 30, 20, 50}์ธ ๊ฒฝ์ฐ
๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ A = {10, 20, 10, 30, 20, 50} ์ด๊ณ , ๊ธธ์ด๋ 4์ด๋ค.
๋์ ๊ณํ๋ฒ(Dynamic Programming) ๋ฐฉ์์ ์ฌ์ฉํ๋ค.
๐ญ ํ์ด ๊ณผ์
์๊ฐ๋ณด๋ค ํ์ด๊ณผ์ ์ ๊ฐ๋จํ๋ค.
๊ณ์ํด์ DP ๋ฌธ์ ๋ฅผ ํ์ดํ๋ฉฐ ํ์ด ์ ๊ทผ ๋ฐฉ์ ๊ฐ์ ์ ์ก๋ ๊ฒ ์ค์ํ ๊ฒ ๊ฐ๋ค.
๋์ ๊ณํ๋ฒ ํ์ด
์์ฑ ์ธ์ด: C++
#include <cstdio>
using namespace std;
int longestSeqLength(int (*dpArr)[1010], int arrSize) {
int max = 0, longest = 0;
for (int i = 0; i < arrSize; ++i) {
for (int j = 0; j < i; ++j) {
if ((*(dpArr))[i] > (*(dpArr))[j]) {
if ((*(dpArr + 1))[j] > max) {
max = (*(dpArr + 1))[j];
}
}
}
(*(dpArr + 1))[i] = max + 1;
if (longest < (*(dpArr + 1))[i])
longest = (*(dpArr + 1))[i];
max = 0;
}
return longest;
}
int main() {
int arrSize = 0, answer = 0;
int dpArr[2][1010] = {0,};
scanf("%d", &arrSize);
for (int i = 0; i < arrSize; ++i) {
scanf("%d", &dpArr[0][i]);
}
answer = longestSeqLength(dpArr, arrSize);
printf("%d\n", answer);
return 0;
}
Max: 0, Longest: 1
10 | 20 | 10 | 30 | 20 | 50 |
1 |
์ฒซ ๋ฒ์งธ ์๋ ์๊ธฐ ์์ ๋ฐ์ ์์ผ๋ฏ๋ก ์ต๋ ๊ธธ์ด๊ฐ 1์ด๋ค.
Max: 1, Longest: 2
10 | 20 | 10 | 30 | 20 | 50 |
1 | 2 |
๋ ๋ฒ์งธ ์๋ ์์ ์ ์ต๋ ๊ธธ์ด๊ฐ 1 ์ด๋ฏ๋ก ์์ ์ ํฌํจํด์ ์ต๋ ๊ธธ์ด๊ฐ 2์ด๋ค.
Max: 0, Longest: 2
10 | 20 | 10 | 30 | 20 | 50 |
1 | 2 | 1 |
์ธ ๋ฒ์งธ ์๋ ์์ ๋ณด๋ค ์์ ์๊ฐ ์์ผ๋ฏ๋ก ์ต๋ ๊ธธ์ด๋ 1์ด๋ค.
Max: 2, Longest: 3
10 | 20 | 10 | 30 | 20 | 50 |
1 | 2 | 1 | 3 |
๋ค ๋ฒ์งธ ์๋ ์์ ์ ์ต๋ ๊ธธ์ด๊ฐ 2 ์ด๋ฏ๋ก ์์ ์ ํฌํจํด์ ์ต๋ ๊ธธ์ด๊ฐ 3์ด๋ค.
Max: 1, Longest: 3
10 | 20 | 10 | 30 | 20 | 50 |
1 | 2 | 1 | 3 | 2 |
๋ค์ฏ ๋ฒ์งธ ์๋ ์์ ์ ์ต๋ ๊ธธ์ด๊ฐ 1 ์ด๋ฏ๋ก ์์ ์ ํฌํจํด์ ์ต๋ ๊ธธ์ด๊ฐ 2์ด๋ค.
Max: 3, Longest: 4
10 | 20 | 10 | 30 | 20 | 50 |
1 | 2 | 1 | 3 | 2 | 4 |
๋ง์ง๋ง ์๋ ์์ ์ ์ต๋ ๊ธธ์ด๊ฐ 3 ์ด๋ฏ๋ก ์์ ์ ํฌํจํด์ ์ต๋ ๊ธธ์ด๊ฐ 4์ด๋ค.
๋งค ์ฐจ๋ก๋ง๋ค ์ต๋ ๊ธธ์ด๋ฅผ ๊ฐฑ์ ํ ๊ฒฐ๊ณผ, 4๊ฐ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ ๊ธธ์ด์์ ์ ์ ์๋ค.
๐ ๋ฐฐ์ด ์
ํ๊ธฐ๊ฐ ์์ํ๋ฉด์ ๊ฝค ์ค๋๋ง์ ๋ฐฑ์ค ๋ฌธ์ ๋ฅผ ํผ ๊ฒ ๊ฐ๋ค.
๋ค์ ํ์ด๋ณด๋ DP ํ๋ ์ ๊ทผ ๋ฐฉ๋ฒ์ด ๊ธฐ์ต๋๊ธฐ ์์ํ๋ ๊ฒ ๊ฐ๋ค.
์์ฃผ, ๊พธ์คํ ๋ฌธ์ ํ์ด๋ฅผ ํ๋ ๊ฒ์ด ์ค์ํ ์ด์ ๋ฅผ ๊นจ๋ซ๊ฒ ๋๋ค.