PS
BOJ 2579 계단 오르기
boj 2579 계단 오르기 문제의 조건에 따라 마지막 계단은 무조건 밟아야한다. 계단은 연속으로 두번까지 밟을 수 있다. 마지막 계단을 밟는데, 그 마지막 계단이 연속으로 밟은 첫번째 계단이냐 두번째 계단이냐로 경우의 수를 나눌 수 있다. 이를 바탕으로 테이블을 정의해보자. D[i][1] = 마지막 계단이 i번째 계단이고 1개의 계단을 연속으로 밟은 경우, 계단 점수 합의 최댓값 D[i][2] = 마지막 계단이 i번재 계단이고 2개의 계단을 연속으로 밟은 경우, 계단 점수 합의 최댓값 D[i][1]의 경우는 i-1번째 계단을 밟지 않으므로, 마지막 계단이 i-2번째 계단일 경우의 계단 점수의 최댓값에서 i번째 계단 점수를 더하면 된다. D[i][2]의 경우는 i-1번째 계단을 무조건 밟고, i-2번째 ..
BOJ 1912 연속합
boj 1912 연속합 간단한 DP 문제이다. a[i]는 수열이 담긴 배열이고, 테이블로 D[i]는 i번째 원소를 마지막으로 하는 연속된 수열 합의 최댓값이라고 정의한다. 합이므로 초기 값은 원소 자기 자신의 값이다. 그러므로 D[i] = a[i]로 초기화한다. 수열이 연속된다는 것을 인지하면 D[i] = max(D[i], D[i-1] + a[i]) 이라는 점화식이 쉽게 만들어진다. 각 수는 -1000에서 1000 사이이 수 이므로 ans는 초기 값으로 -1001을 주었다. 위 내용을 바탕으로 코드를 구현해보자. #include #include using namespace std; int n; int a[100005]; int D[100005]; int ans = -1001; int main(void) ..
BOJ 11054 가장 긴 바이토닉 부분 수열
boj 11054 가장 긴 바이토닉 부분 수열 boj 11503 가장 긴 증가하는 부분 수열 문제를 풀었다면 쉽게 이해할 수 있는 문제이다. 아래의 풀이를 참고할 것을 추천한다. boj 11503 가장 긴 증가하는 부분 수열 문제 풀이 바이토닉 수열이 기준이 되는 수를 중심으로 증가하는 수열에서 감소하는 수열로 바뀐다는 것에 포인트를 잡았다. 바이토닉 수열의 길이의 최댓값 = (기준 수까지 증가하는 수열 길이 + 기준 수부터 감소하는 수열 길이)의 최댓값라고 이해할 수 있다. Dinc[i]는 i를 마지막 원소로하는 증가 수열 길이의 최댓값이고, Ddec[i]는 시작 원소를 i로 하는 감소 수열 길이의 최댓값이다. 쉽게 구현하기 위해 Ddec[i] 표현을 달리해보자. 수열이 담긴 배열 a[i]를 거꾸로 끝..
BOJ 11722 가장 긴 감소하는 부분 수열
boj 11722 가장 긴 감소하는 부분 수열 boj 11053 풀이 보기 boj 11053 문제에서 증가하냐 감소하냐의 차이만 있을 뿐 다른 것은 다 똑같은 문제이다. 그렇기에 점화식을 실행하는 2가지 조건 중 a[i] > a[j]만 a[i] > n; for (int i = 1; i > a[i]; for (int i = 1; i = D[i]) D[i] = D[j] + 1; } mx = max(mx, D[i]); } cout
BOJ 11055 가장 큰 증가 부분 수열
boj 11055 가장 큰 증가 부분 수열 boj 11053 가장 긴 증가하는 부분 수열과 풀이가 비슷한 문제이다. 다만 11053에서는 길이였다면 이번 문제에서는 수열의 합이 최대가 되어야한다. D[i]는 i번째 원소를 마지막으로 하는 증가 부분 수열의 합 중 최댓값이라고 정의한다. a[i]는 수열을 담는 배열이다. 문제에서 주어진 수열을 예시로 들자면, 아래와 같이 작동해야한다. 코드를 먼저 보고 코드에 대해 설명하겠다. #include #include using namespace std; int n; int a[1005]; int D[1005]; int mx; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int ..