안녕하세요, 오랜만에 돌아온 쏘코입니다.
왜 그동안 돌아오지 못했는가..에 대해서 변명하자면
문제가 너무 어려워서 오래 걸렸습니다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
처음 푸는 레벨4 문제다보니 시행착오가 많았습니다. 너무 어렵게 생각했나..
어쩔 수 없이 검색으로 약간의 도움을 받았습니다.
바로 문제부터 살펴보시죠!
출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, programmers.co.kr/learn/courses/30/lessons/42897
코딩테스트 연습 - 도둑질
도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한
programmers.co.kr
목차
0. 문제 설명
도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.
각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.
0.0. 제한사항
- 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
- money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.
0.1. 입출력 예
| money | return |
| [1, 2, 3, 1] | 4 |
1. 풀이 과정
처음에는 큰 순서대로 정렬한 후에 큰 친구들을 빼려고 했습니다. 그렇게 했더니 index에 관한 문제들이 여러 가지 발생하더라구요. 그리고 무턱대로 큰 수부터 빼버리면 [3,4,5,6,5,1], 13과 같은 문제에서 예외사항이 발생하게 됩니다.
그래서 두 번째로 생각한 알고리즘은 훔칠 집 재산 - 못훔치는 이웃 2집의 재산을 찾아서 가장 큰 친구부터 지우는 것이었습니다. 하지만 이 알고리즘은 테스트케이스에서부터 동작시간의 벽에 막혀버렸습니다. 지금 생각해도 좀 이상한 알고리즘이었네요.
마지막으로 해결한 알고리즘은 dp의 기본인 케이스 순서대로 해결하는 것이었습니다. 첫 번째 집을 고르는 경우와 고르지 않는 경우로 나눠서 생각했습니다.
먼저 dp라는 배열을 하나 만듭니다. 이 배열에서 각 index에 위치한 값은 money라는 vector가 해당 index까지만 존재할 때 털 수 있는 최대한의 돈을 뜻합니다.
첫 번째 집을 고르면 맨 마지막과 두 번째 집은 고를 수 없게 됩니다. 첫 번째 집을 거르면 두 번째 혹은 세 번째 집을 고르게 됩니다.
첫 번째 집을 고르는 경우부터 살펴보겠습니다. dp[0]은 집이 하나밖에 없으니 당연히 그 집을 털어서 money[0]을 획득합니다. dp[1]은 첫 번째 집을 털었으니 당연히 두 번째 집은 털지 못하므로 그대로 money[0]이 됩니다.
그 다음부터는 for문을 통해 반복되는 점화식이 들어갑니다. money.size()-1 미만까지 i를 반복해서 for문을 돌려줍니다.
dp[2]를 살펴보면 세 번째 집까지 존재할 때 dp[0] + money[2](첫 집에서 턴 돈의 양 + 세 번째 집에서 털 수 있는 돈의 양)과 dp[1]을 비교해서 큰 값이 들어가게 됩니다. 여기서는 dp[1]이 dp[0]과 같으므로 dp[2]는 강제로 dp[0] + money[2]가 됩니다. 첫 집을 무조건 터니 세 번째 집을 턴다고 생각하는 것이죠. 다만 만약 집이 3개만 있다면 money.size-1까지만 돌기 때문에 dp[0], money[0]이 그대로 answer이 됩니다. 끝까지 돌려서 마지막에 나온 dp[money.size()-2]를 answer에 넣어줍니다.
두 번째는 첫 번째 집을 고르지 않는 경우입니다. 첫 번째 집은 있어도 털지 않기 때문에 dp[0]은 0이 됩니다. 대신 dp[1]은 첫 집을 털지 않았으니 두 번째 집을 털 수 있어서 money[1]이 됩니다. 다시 위에서 돌린 for문이 그대로 돌아갑니다. 다만 여기서는 마지막 집을 털 수 있기 때문에 money.size() 미만까지 i를 반복해서 for문을 돌려줍니다.
다시 현재 i가 2이라고 가정합시다. dp[2]는 dp[0]+money[2]와 dp[1]중 큰 친구가 됩니다. dp[0]이 0이므로 이 max식은 money[1]과 money[2]의 비교와 같습니다. 두 번째 집과 세 번째 집 중 더 돈이 많은 집을 털게 되는 것이죠. 그 이후는 같습니다. 반복하면서 다음 집을 털 지 다다음 집을 털 지 고르게 됩니다.
이 과정을 마치고 남은 dp[money.size()-1]을 아까 첫 번째 집을 털었을 때의 결과인 answer와 비교합니다. 그 중에서 큰 값이 우리가 원하는 훔칠 수 있는 돈의 최댓값이 됩니다.
2. 소스 코드
2.0. 정답 코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> money) {
int answer = 0;
int dp[1000000]; // 각 index의 값은 index까지 털 수 있는 최대한의 돈
// 0. 첫 번째 집을 고르고 마지막 집을 고르지 않는다 (money.size()-1까지 돌림)
dp[0] = money[0];
dp[1] = money[0];
for(int i = 2; i < money.size()-1; ++i)
dp[i] = max(dp[i-2] + money[i], dp[i-1]);
answer = dp[money.size()-2];
// 1. 첫 번째 집을 고르지 않는다 -> 이 말은 2번째 혹은 3번째 집부터 턴타는 말과 같음(money.size()까지 돌림)
dp[0] = 0; // 첫번째 값이 있어도 안 훔칠거니까!!
dp[1] = money[1];
for(int i = 2; i < money.size(); ++i)
dp[i] = max(dp[i-2] + money[i], dp[i-1]);
answer = max(answer, dp[money.size()-1]);
return answer;
}
2.1. 시행착오 코드1
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> money) {
int answer = 0;
int chk[1000000] = {0,};
vector<int> sortmoney;
sortmoney.resize(money.size());
// 복사함
copy(money.begin(), money.end(), sortmoney.begin());
// 정렬함
sort(sortmoney.begin(), sortmoney.end(), greater<int>());
// 값을 찾음
for(int i = 0; i < money.size(); ++i){
int temp = find(money.begin(), money.end(), sortmoney[i]) - money.begin();
if(chk[temp] == 0){
answer += money[temp];
chk[temp] = 1;
if(temp != 0)
chk[temp-1] = 1;
else
chk[money.size()-1] = 0;
if(temp != money.size()-1)
chk[temp+1] = 1;
else
chk[0] = 1;
}
}
return answer;
}
2.2. 시행착오 코드2
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> money) {
int answer = 0;
int idxsize = money.size()-1;
int cal; // 가운데-(앞+뒤) 계산값
int calidx = -1;
bool chk = false;
while(chk == false){
int cal = -10000;
int calidx = -1;
bool chk = true;
for(int i = 0; i < money.size(); ++i){
if(i == 0){
if(cal < money[0] - money[idxsize] - money[1]){
cal = money[0] - money[idxsize] - money[1];
calidx = i;
}
}
else if(i == idxsize){
if(cal < money[i] - money[i-1] - money[0]){
cal = money[i] - money[i-1] - money[0];
calidx = i;
}
}
else {
if(cal < money[i] - money[i-1] - money[i+1]){
cal = money[i] - money[i-1] - money[i+1];
calidx = i;
}
}
}
for(int i = 0; i < money.size(); ++i){
if(money[i] != 0){
chk = false;
break;
}
}
if(chk == true)
break;
answer += money[calidx];
money[calidx] = 0;
if(calidx == 0)
money[idxsize] = 0;
else
money[calidx-1] = 0;
if(calidx == idxsize)
money[0] = 0;
else
money[calidx+1] = 0;
}
return answer;
}
3. 후기
한 3일동안 일하면서 계속 생각했는데 못풀었는데, 검색해보니 쉽게 푼 분들이 많아서 굉장히 당황했습니다. 물론 객관적으로 봐도 level 4에서는 쉬운 문제의 축에 속하겠지만, dp가 들어가면 아이디어를 떠올리는 것부터가 굉장히 어려워지는 것 같습니다. 매번 고레벨 문제에 혼나다 보면 조금은 나아지겠죠..?
최근댓글