💎 첫 velog 게시글 🎉🎉
-
3학년 2학기 겨울 방학 기간이 시작되고 velog를 새롭게 시작하게 되면서 앞으로 알고리즘 문제, 그리고 프론트엔드 개발자로서 사용하고 있는 프레임워크 또는 생기는 문제점 등등 들을 velog에 기록해두고 정리해보고자 시작하게 되었다.
-
현재 내 백준 티어는 실버 1이며 주로 실버3~ 골드3 사이에 있는 문제들을 풀어보고 어떤 점들이 내가 취약하고 해결하기 힘들었는지 또는 어떤 접근에서 다른 팁들을 얻을 수 있었는지 코딩테스트를 준비하면서 기록하는 것이 도움될 것이라고 생각된다.
-
부족하다고 생각되는 부분들이 너무나도 많기 때문에 쉬운 문제 부터 어떤 유형이 있는지 확실히 기록해보고 꾸준히 velog에 작성해서 나에게 도움이 될 수 있도록 해보자.
💎 문제
상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
N = 7인 경우에 다음과 같은 상담 일정표를 보자.
| 1일 | 2일 | 3일 | 4일 | 5일 | 6일 | 7일 | |
|---|---|---|---|---|---|---|---|
| Ti | 3 | 5 | 1 | 1 | 2 | 4 | 2 |
| Pi | 10 | 20 | 10 | 20 | 15 | 40 | 200 |
1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.
상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.
또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.
퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.
상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
💎 입력
첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)
💎 출력
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
💎 풀이 방법
dinamic programming을 이용한 문제로 해결할 수 있었다.
나는 주로 배열에 관한 문제나 정보를 저장하는 방법을 사용함에 있어서 vector를 이용하기 때문에(크기 조정이 편해서) vector를 사용하였고 어떤 식으로 dp의 초기 값을 설정하고 문제를 풀지 고민하였다.
이 문제에서는 만약 N일의 기간이 있을 때 상담을 하여 최대 수익을 낼 수 있는 것을 구해야 하기 때문에 현재까지 구한 담을 수 있는 최대의 수익과 현재 구하는 dp의 값에 새로운 추가된 상담의 수익까지 더한 것을 비교한 것으로 결과를 구할 수 있었다.
만약 이를 top down방식을 이용하여 N일차부터 차례대로 dp를 구해낸다면 단O(n)번의 시간 복잡도를 구할 수 있기 때문에 효율적이라고 생하였고 N일차의 dp부터 1일차의 dp를 구하는 방식을 활용하였다.
for(int i = N; i >= 1; i--){
if(i + T[i] - 1 > N){
dp[i] = dp[i + 1];
continue;
}
dp[i] = max(dp[i + T[i]] + P[i], dp[i+1]);
}위와 같이 만약 현재 구하는 N일차의 상담의 상담기간을 수행할 수 있으려면 반드시 하루의 상담기간을 가져야한다. 따라서 i + T[i] - 1로 N일차의 상담기간과 현재 검사하는 상담일자 i를 더한 것에 수행해야하는 하루를 뺀 것이 전체 상담할 수 있는 기간인 N일보다 크다면 이는 수행할 수 없는 상담이기 때문에 앞선 dp의 값을 그대로 넣어주어 변화가 없음을 표현한다.
만약 수행할 수 있는 상담이라면 앞선 dp의 값과 크기를 비교해서 더 큰 수익을 현재 dp의 값에 저장해야 하는데 이는 앞서서 계산한 dp의 값인 수행이 가능했던 상담의 연장선상으로 수익을 더해주어야하기 때문에 dp[i + T[i]] + P[i]으로 현재 구하는 상담일자에서 수행되는 상담의 기간을 더해준 그날의 dp의 값에 현재 구하는 상담일자에 해당하는 수익의 값을 더해준 것이다. 따라서 이 dp와 이후의 dp값을 비교해서 더 큰 것을 현재 dp에 저장해주면 된다.
💎 전체 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector <int> T(16);
vector <int> P(16);
vector <int> dp(16);
int main(int argc, const char * argv[]) {
int N;
int tmp1,tmp2;
cin >> N;
for(int i = 1;i <= N;i++){
cin >> tmp1 >> tmp2;
T[i] = tmp1;
P[i] = tmp2;
}
for(int i = N; i >= 1; i--){
if(i + T[i] - 1 > N){
dp[i] = dp[i + 1];
continue;
}
dp[i] = max(dp[i + T[i]] + P[i], dp[i+1]);
}
cout << dp[1] << "\n";
return 0;
}
💎 고민
이게 확실히 dp문제는 가장 많이 풀어보기도해서 시간만 오래 주어진다면 해결해낼 수 있겠다는 생각은 있는데 빠르게 초기값을 어떻게 넣어주고 시간 복잡도도 효율적으로 고민해서 도출하는 과정에 따라 까다로울 수 있는 것 같다. dp문제는 식을 끄적이면서 풀면 도움이 많이 됬던 것 같으니깐 손으로 써보면서 규칙을 찾아보는 방법 첫째, 잘 안되면 그 이전과 이후의 값을 이용해보는 문제인지 확인하기 둘째로 접근해보면 오히려 쉽게 풀리는 경우가 많으니깐 꼭 많이 풀어보고 아 이건 dynamic programming으로 풀면 되겠다를 감 잡아야겠다.
화팅
