벌꿀 채취
순열과 조합, 재귀함수, Brute force를 이용한 문제였다. 조금만 집중해서 제대로 풀면 풀만한 문제였다. 집중을 제대로 못/안한 건지 그냥 못 푼 건지.
내가 접근한 방법, 알고리즘 큰 틀에서, 일꾼1과 일꾼2를 동시에 선택해줘야하기 때문에 일꾼1을 먼저 선택한 다음 일꾼2를 선택한다. 슬라이딩 윈도우 기법으로 일꾼1의 윈도우를 먼저 설정하고 난 후, 동일한 2중 반복문 내에서 일꾼2의 윈도우를 설정하는 것으로 구현했다. =>개선 방안 : 동일한 2중 반복문 내에서 각각의 부분해를 구하고, 이 부분해의 최댓값으로 도출하는 부분이 다소 복잡해서 따로 메서드로 빼는 것이 코드가 간결해질 것 같다.
일꾼2가 윈도우를 시작할 때, 일꾼1의 윈도우가 끝나는 점에서 M개가 연속된 윈도우여야하기 때문에, 일꾼1의 윈도우 끝점 + M이 N 범위이내인지 확인해야한다. 또한, 선택이 겹치면 안 되기 때문에 각 일꾼이 어떤 위치 선택하면 boolean 2차원 배열에 true로 마킹함으로써 중복방지처리해줬다.
일꾼1의 윈도우와 최대부분합 구하기
일꾼2의 윈도우와 최대부분합 구하기
못 푼 이유 일꾼1과 일꾼2 각각 최대가 되는 부분합을 구할 때, 부분합만 저장하는 것이 아니라 그때의 꿀양도 저장할 필요가 있다고 생각했다. 따라서 부분합만 최댓값으로 갱신하는 것이 아니라, 부분합을 이루는 꿀양을 저장하는 컬렉션 또한, 최댓값으로 이루어진 컬렉션으로 갱신해야하는 것이다. 정수값을 최댓값으로 갱신하는 경우는 많지만, 컬렉션을 최대가 되는 컬렉션으로 갱신한다는 것은 한번도 해본 적도, 들어본 적도 없었기에 매우 생소했다.(이 때부터 오답의 기운이 느껴졌나.) 그리고 하나의 2 중 반복문으로 모든 로직을 커버할 수가 있는지 의문이다. 예를 들어 N=10,M=5,C=13 이고, 일꾼1이 (0,5)에서 시작하는 최대합 구간을 선택했다고 하자. 그러면 일꾼2는 0번째 행에서는 더이상 시작점을 선택할 수 없기 때문에 1행으로 넘어가서 0번째 열부터 시작점을 선택할 수가 있다. 이 때 2중 반복문 변수 (i,j)는 (0,5)인데 일꾼2의 최대합을 구하기 위해서는 (1,0) 부터 반복해야한다. 그러므로 하나의 2중 반복문 만으로 일꾼1과 일꾼2의 부분합과 그 최댓값 부분합을 구하기에는 무리가 있다. =>정답 솔루션은 재귀함수와 순열조합을 이용하여 이러한 부분을 어떻게 풀어나갔을까? 이 부분이 핵심이다.
정답 솔루션 로직은 간단하다. 일꾼1과 일꾼2 각각 조합으로 최대 부분합을 갖는 모든 가능한 경우에 대해 최대 부분합을 구하고, 그 때의 점수값을 계산한다.=>재귀함수로 구현 가능하고, 그 칸을 선택할 때마다 다음 재귀함수 호출시에, 매개변수로 그때까지 합산한 점수값(제곱값)을 함께 넘겨준다.
소스코드를 편협하게 변수값이 하나하나 어떻게 변하는지 보지말고, 전체적인 로직을 이해!
알고리즘 핵심 : 각 M개칸 구간마다 최대합을 미리구해놓고, 일꾼1,2의 부분합을 선택한다.⭐️⭐️⭐️⭐️⭐️
해당 구간에서 얻을 수 있는 최대수익을 먼저 계산한다. M과 C를 알고 있기 때문에 전체 2차원 배열에서 연속된 M개칸 구간마다 합을 구할 수 있다. (i,j)에서 시작하는 합 중 최댓값을 Profit[ i ][ j ]에 저장한다. =>Profit[ i ][ j ]는 (i,j)에서 시작하는 최대합을 의미하기 때문에 일꾼1과 일꾼2는 선택점(a,b)만 선택해서 최대이익합을 구하면 된다!
1을 이용하여 일꾼1의 부분최대합을 먼저 선택하고, 그때의 시작점이후부터 일꾼2의 부분최대합을 선택한다. 주의해야할 점!구간이 겹치면 안되기 때문에 일꾼1이 (a,b)를 시작점으로 하는 최댓값 Profit[a][b]를 선택하면 일꾼ㄴ2는 (a,b+M)부터 시작점 선택할 수 있다!⭐️⭐️⭐️⭐️⭐️ 만약 a행에서 N열 이내에 M개구간 선택할 수 없다면 a+1행으로 넘어가고, 0열부터 최대합구간 선택한다! =>combination 재귀함수 구현 환상적임. 처음엔 열 시작 반복문이 b+M으로 시작하다가, 열 반복이 끝나면 이 열 반복문의 반복변수를 0으로 초기화한다. 스고이...
2번째 풀었을 때 틀린 이유 : 최대합을 구하는 재귀함수 profitSubset
배열 인덱스 초과 : 재귀함수 profitSubset은 y를 1씩 증가시켜서 재귀함수 호출&실행하기 때문에 정답 찾은 조건에서 y는 인덱스를 초과해버린다. 애초에 정의한, Profit[i][j]는 (i,j)에서 시작하는 구간의 최대합을 저장하는 것이기 때문에 정답을 찾은 경우, Profit[i][j]가 아니라 Profit[i][j-M]에 저장해야한다!
(i,j)에서 시작하는 M개 구간에서 각 칸을 합으로 넣을지 말지를 결정해야한다. 이 때, 문제 조건인 채취하는 벌꿀 양이 C이내인 조건을 만족해야하기 때문에 조건 체크용 벌꿀합 한산양 sum1과, 그때의 최대이익합인 sum2 두 개의 변수가 필요하다! sum1은 조건 체크용이고, sum2가 우리가 구하고자하는 최대이익합이다!Profit[i][j-M]에 저장될 값!
Last updated