반응형 [백준]214 [BaekJoon/백준] 2565번 | 복습 1회 완료 LIS ( 최장증가수열 ) 응용문제다. 11053번, 11054번과 같은 LIS 카테고리의 문제. 처음에는 아무것도 신경쓰지않고, 내키는대로 문제를 풀어봤다. (최장증가수열문제라는 것 인지하지 않고) 정답(X) #include int a[100][4]; int N; int MAX = 0; int MAX_index = -1; int count = 0; int schedule() { int k = 0; for(int i = 0; i a[j][1]) || (a[i][0] .. 2021. 1. 6. [BaekJoon/백준] 11054번 | 복습 1회 완료 LIS ( 최장증가수열 ) 응용문제. 11053번의 응용 문제. 11053번은 앞에서 뒤로만 했는데, 11054번은 뒤에서 앞으로도 한번 해주면 된다. #include int N; int a[1000][3]; int main() { int i, j, max = 1; // max = 1은 N = 1은 무조건 충족하므로 기본값. scanf("%d", &N); a[0][1] = 1; for(i = 0; i = 0; j--) { if(a[i][0] > a[j][0] && a[i][1] < a[j][1]) a[i][1] = a[j][1]; } a[i][1]++; // 자신.. 2021. 1. 4. [BaekJoon/백준] 11053번 / 순열 조합은 동적계획법인가? | 복습 1회 완료 LIS( 최장증가수열 ) 문제다. 이 문제를 보고는 곧바로 풀이가 떠올랐다. 원리가 간단해보였다. 하지만 갈등했다. 문제는 명칭의 문제였다. 여태까지 풀어온 방식대로 뭔가 동적계획법 같은 느낌으로 풀어볼까 라는 마음으로 시작했는데, 내가 지금 생각해낸 방식이 동적계획법을 이용한 풀이가 맞는지에 대한 강박이 생겼다. '동적계획법' 카테고리에 소속되어 있는 문제인데, 내가 푼 풀이는 뭔가 여태까지 풀어온 동적계획법과는 느낌이 달랐다. 그래도 일단 짜봤다. 내방식대로. 그리고 제출에 넣어봤다. 정답 받았다. 그리고 사람들의 풀이를 봤다. 나와 동일했다. #include int N; int a[1000][2]; int main() { int i, j, max = 1; // max = 1은 N = 1은 무조건 충.. 2021. 1. 4. [BaekJoon/백준] 2156번 | 복습 1회 완료 이전 계단문제인 2579번과 아주 유사한 문제다. (계단 문제 응용버전이라고 볼 수 있음) 기존의 계단 오르기 문제는 아래와 같다. A B C D가 있을 떄, D까지 오기 위한 방법은 1. B까지 오른 뒤 D를 오른다. 2. A까지 오른 뒤 C로 간 뒤 D를 오른다. 둘 중 최댓값을 선택 하지만 해당 문제는 가장 마지막 계단의 계산값을 찾는 게 아니라, 각 계단까지 오르는데의 최댓값을 계단별로 비교해서 최댓값을 얻어낸다. ex) A B C D E가 있을 때, D까지 최대로 오르는 것이 E까지 최대로 오르는 것 보다 값이 클 수가 있다. 1 2 9 3 2 -> D 까지 최댓값 13, E까지 최댓값 12 (기존 계단문제 기반 예시) 기존 계단문제는 이런 값을 도출하게 된다. 여기서 조금 응용을 해야 이 문제.. 2021. 1. 3. 이전 1 ··· 35 36 37 38 39 40 41 ··· 54 다음 반응형