문제 이해 단계
집이 원형으로 배치되어 있고,
한 집을 선택하면 양 옆에 있는 집을 선택할 수 없게 된다.
이러한 조건일 때 얻을 수 있는 가장 많은 숫자 합을 고르는 문제
문제는 엄청나게 간단하다.
문제 접근 단계
일단 배치를 신경 쓰지 말고, 그냥 일반적인 문제처럼 일렬로 집이 있다고 생각해 보자.
그러니까 해당 문제에서 원으로 배치된 것을
어떤 집을 기준으로 일렬로 배치한 것이다.
입력을 주어진 그대로 일렬로 배치해 봤다.
구해야 하는 것은 이 중 최적의 집들을 선택해서 최댓값을 구하는 것이다.
3번 집부터 시작한다고 생각하자.
해당 문제에서 집은 최소 3개라고 했으니 3개부터 살펴본다.
그러니까 현재는 왼쪽에 있는 [2,3,4] 집 밖에 없다고 생각하는 것이다.
집 하나를 고르면 양 옆은 고를 수 없기 때문에 3개일 때는 하나밖에 고르지 못한다.
즉 가장 높은 수를 골라야 하므로 답은 4이다.
이를 House [3] = 4로 표기하겠다.
이는 "세 번째 집까지 진행했을 때의 최대 합은 4"를 의미한다.
4번까지 진행했을 때, 집이 [ 2, 3, 4, 2 ] 총 4개가 있다고 해보자.
끝에서부터 생각해 보자.
4번까지 진행했을 때 가능한 경우는 뭐가 있을까?
일단 두 가지가 있다.
1. 4번 집 선택 O
2. 4번 집 선택 X
4번 집 선택 O
4번 집을 선택한 케이스부터 살펴보면,
앞에서 4번 집까지 올 수 있는 경우는 하나이다.
4번 집 두 칸 전에 있는 2번 집에서 올 수 있고
3칸 떨어진 첫 번째 집에서 올 수 있다.
그런데 원래 이는 원형이라고 상정했기 때문에
사실상 네 번째 집 오른쪽에 첫 번째 집이 있는 것이기 때문에 안된다.
그래서 위의 경우 하나뿐이다.
그래서 위의 경우에는 House [4] = 3 + 2이다.
4번 집 선택 X
4번 집을 선택하지 않았다면 해당 경우에는 한 가지이다.
원래라면 네 번째 집과 1칸 떨어져 있는 집과 2칸 떨어져 있는 둘 다 되지만,
2번째 집을 선택하면 하나밖에 고르지 못하기 때문에 한 가지밖에 안된다.
그래서 이 때는 House [4] = 6이다.
결과적으로 House [4]는 숫자가 더 큰 6이 답이 된다.
여기서는 확실한 일반화가 되지 않을 것 같아서
6번째 집을 해보면서 다시 생각해 보자.
6번 집 선택 O
여섯 번째 집에 도달하기 위해서 가능한 경로는 다음과 같을 것이다.
여기서 알 수 있는 것은 동일한 조건이 계속해서 반복돼서 나타난 것이다.
6번 집 선택 X
위도 마찬가지로 이런 식으로 나오게 된다.
모든 경우의 수를 살펴보니 동일한 조건이 반복되고,
부분적인 반복의 답이 전체적인 반복의 답이 된다.
즉 해당 문제는 다이내믹 프로그래밍으로 접근하는 것이 맞는 것 같다.
그래서 점화식을 만들려고 하는데 한 가지 문제가 있다.
원형으로 배치되어 있다는 것이다.
점화식을 세우려면 수식이 일정해야 하는데 여기서는 그렇지 않다.
왜냐하면 원형이기 때문에 리스트 끝에 집이 변경될 때마다
처음에 있는 집이 선택될 수도 있고, 선택 안될 수도 있어서 일정하지 않다는 것이다.
그래서 해당 문제를 원이 아닌 직선으로 만들어주었다.
dp [i][0] = i번째 집을 선택하지 않았을 때의 최대합(i까지 진행함)
dp [i][1] = i번째 집을 선택했을 때의 최대합(i까지 진행함)
내가 이렇게 한 이유는 아래 그림에서 설명한다.
두 그림은 완벽히 같다.
다른 점은 탐색 범위인데, 위는 집이 [2,3,4] 아래는 집이 [2,3,4]이다.
그래서 결과가 다르게 나온다.
그런데 사실 원래대로 라면
세 번째 집 뒤에는 네 번째 집이 존재하기 때문에 첫 번째 집을 골라도 된다.
하지만 세 번째 집 때는 그걸 몰랐기 때문에 그렇게 못한 것이다.
만약 그걸 사전에 정리해 준다면
이전에 House [3]을 House [4] 계산에 사용할 수 있게 된다.
왜냐하면 [2,3,4,2]를 사용하는 동일한 조건에서 사용한 것이기 때문이다.
그래서 맨 처음 2가지로 분리했다.
1. 마지막 집을 포함할 때
마지막 집을 포함하기 때문에 가장 앞에 있는 집과 마지막 앞에 집은 포기한다.
이렇게 정리해 줌으로써 이제 원형이 아닌 선형 리스트로 생각해도 된다.
이런 양상이 나타나게 되는데,
어렵게 보이지만 결국엔 똑같은 반복이 반복되는 것이다.
i까지의 최대합을 DP [i]로 표현한다면
DP [i] = max(DP [i-2], DP [i-3]) + i번째 집의 값
2. 마지막 집을 포함하지 않을 때
마지막 집을 포함하지 않는다고 첫 집을 무조건 포함하는 것은 아니다.
마지막 집만 포함하지 않을 채로 선형 탐색을 시작하면 된다.
이를 제외하고서는 집을 포함한 것과 똑같다.
DP [i] = max(DP [i-2], DP [i-3]) + i번째 집의 값
문제 구현 단계
#include <string>
#include <vector>
using namespace std;
int solution(vector<int> money) {
int dp[1000000][2];
int answer = 0;
// 마지막 집 포함x 일때 0,1,2 초기화
dp[0][0] = money[0];
dp[1][0] = money[1];
dp[2][0] = money[0]+money[2];
// 마지막 집 포함O 일때 1,2,3 초기화
// 첫 집을 제외하기 때문에 1부터 초기화
dp[1][1] = money[1];
dp[2][1] = money[2];
dp[3][1] = money[1]+money[3];
// 집이 3개밖에 없을 때가 가장 높은게 답
if(money.size() == 3){
answer = (money[0],money[1]);
answer = (answer,money[2]);
return answer;
}
for(int k = 0; k < 2; k++){
// 마지막 집은 따로 처리해줌
for(int i = 2; i < money.size()-1; i++){
// 마지막 집 있을 때
if(k == 1){
// 처음 3개의 집, 마지막 앞에 집은 패스
if(i < 3 || i >= money.size() - 2) continue;
}
// i-2와 i-3 중 큰 수 선택
dp[i][k] = max(dp[i-2][k],dp[i-3][k]) + money[i];
answer = max(answer,dp[i][k]); // 가장 큰 수 answer
}
}
// 마지막 집 있을 때의 마지막 수를 더해줌
int idx = money.size()-1;
dp[idx][1] = max(dp[idx-2][1],dp[idx-3][1]) + money[idx];
answer = max(answer,dp[idx][1]);
return answer;
}DP이기 때문에 코드는 그렇게 길지 않다.
반복문을 통해 이를 구현하였다.
구현할 때 처음 3개의 집은 조건을 따르지 않기 때문에 따로 초기화를 해주는데,
이게 또 마지막 집을 포함하냐에 따라 다르기 때문에 따로 처리해줘야 한다.
나머지는 위에서 설명했던 것처럼 i-2와 i-3 중 더 큰 dp를 선택한다.
계속 dp를 돌면서 비교를 통해 제일 큰 수를 선택한다.
시행착오
처음으로 풀어보는 Level 4 문제였는데
6시간 걸린 정도면 괜찮은 건가? 그래도 풀었다는 게 좋았다.
처음에는 마지막 집과 첫 집간의 관계를 통해
점화식을 만들려고 했는데 역부족이었다.
다른 누군가는 마지막집과 첫 집간의 관계를 통해 문제를 풀었을까?
코드가 깔끔하게 나온 거 같진 않아서 불만족스럽다.
클린코드 같은 거 해야 하나.