예시로 이해하기i는 인덱스로 1부터 잡았고,a[i]는 입력되는 값이다.d[i]는 i까지 커지는 부분 수열 합의 최대 값이다. i번째 숫자마다 처음부터 자기자신 (i-1)전까지 숫자를 확인하면서자기보다 작다면 부분수열로 넣을지 말지 판단하면 되는데, 이 때 max를 이용해서 큰 수가 되도록 유지해야한다. 아래 예시를 통해 한 번 이해해보자. 코드#include using namespace std;int n;int a[1002];int d[1002];int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n; for (int i=0;i>a[i]; for (int i=0;i

문제 접근 일단 주어진 테스트 케이스에 맞춰서 상황을 살펴봤다.N = 1)1 / 2/ 3/ 4/ 5/ 6/ 7/ 8/ 9N = 2)10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98 0 - 11 - 0,22 - 1,33 - 2,44 - 3,55 - 4,66 - 5,77 - 6,88 - 7,99 - 8N = 3)101 123 121 234 232 212 210321 323... 보면 자기 자신에 +1,-1 한 숫자들 만큼이 인접한 숫자가 된다.그래서 0이나 9일 떄는 1개씩밖에 못 더해준다. (0일 떄는 -1을 못하고, 9일 떄는 +1을 못하기 떄문)보면 N=2일 때의 값은, N=1인 숫자들에 +2 씩 해주고, 9일 때만 +1 해주면 된다. N이 몇자리 수 이든간에,..

첫 번째 문제 접근 방법와 어려움우선 작은 삼각형을 그려서 실제 값을 기준으로 상황을 살펴봤다. 왼쪽은 주어진 예시 삼각형을 그렸고, 파란색은 인덱스 위치를 작성해봤다.그리고 인덱스 4번 (삼각형에서는 1이라는 값)까지의 최대값을 구하려면왼쪽 위 또는 오른쪽 위 값 중에서 큰 값을 선택해서 자기 자신의 값을 더하면 된다. 그리고 이게 성립하려면, 왼쪽 위 또는 오른쪽 위 값은자기 자신까지 선택된 수의 합이 최대라는 조건을 만족하며 만들어진 값이어야 한다. -> 이 부분이 DP임을 의미한다고 보면 된다!(그냥 한 단계 전의 숫자가 크다고해서, 지금까지의 합이 최대라는 걸 보장하진 못하니까 말이다.) 그래서 아래와 같이 일반화를 했다.D[i] = i번째 수까지 합이 최대인 값을 담는 배열을 생각했다. 하...