Q1. 14501 퇴사 > 문제 링크
문제를 접근하기 위해 규칙을 찾아보았다.
만약 1일차에 상담을 진행한다면, 1일차 상담의 이익 + 4일차(1일차 + 상담을 할 수 없는 3일) 이후 진행한 상담에서의 이익의 합이 최종적으로 상담으로 벌 수 있는 이익이다.
마찬가지로 2일차에 상담을 진행한다면, 2일차 상담의 이익 + 7일차(2일차 + 상담을 할 수 없는 5일) 이후 진행한 상담에서의 이익의 합이 나중에 최종적으로 상담으로 벌 수 있는 이익이다.
그리고 만약 1일차에 상담을 진행하지 않는다면, 나중에 최종적으로 상담으로 벌 수 있는 이익은 2일차 이후 진행한 상담에서의 이익이다.
이런 식으로 상담을 진행 한 상황과, 진행하지 않는 상황의 로직을 분리하여 규칙을 만들 수 있었다.
상담을 진행 한 상황에서의 이익은 그 날의 이익 + (그 날+ 상담을 하지 못하는 날)이후에 진행한 상담에서의 이익, 진행하지 않은 상황에서의 이익은 그 다음날 이후 진행한 상담에서의 이익이 되고, 이를 재귀로 구현할 수 있었다.
#include <iostream>
#include <algorithm>
using namespace std;
int dp[16], t[16], p[16] = { 0, };
int n;
int solve(int i) {
if (i > n) return 0;
int ret = 0;
if (i + t[i] <= n + 1) {
ret = solve(i + t[i]) + p[i];
}
return max(ret, solve(i + 1));
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> t[i] >> p[i];
}
int ans = solve(1);
cout << ans;
}코드를 설명해보면,
n의 값과 각 상담에 대해 몇일간 상담을 진행하는지, 각 상담의 이익을 입력 받는다.
문제에서는 1일차 이후 전체 상담 과정에서의 이익을 요구했으로 solve(1)을 호출하여 수행한다.
solve함수 안에서는 먼저, 들어간 수가 n을 넘는지를 확인한다.
만약 넘는다면 이미 퇴사한 이후니까 0을 반환한다.
n을 넘지 않는 수의 경우에는 해당 일에 상담을 진행하려고 한다면, 시작된 상담일의 종료일이 퇴사일 전인지를 확인한다.
예를 들어 7일차에 상담을 진행하려고 하면 7일차 상담이 2일이 걸리니까 아예 선택을 할 수 없다.
이 조건도 만족시켰다면 해당 일을 선택했을 때의 이익을 "solve(i + t[i](상담이 중단되는 기간)) + 지금 상담에서의 이익"을 통해 구하고,
이를 상담 하지 않았을 때의 이익(하루 뒤 이후의 이익) 과 비교하여 더 큰 값을 결과값으로 지정한다.
이 과정에서 함수는 계속 재귀적으로 호출 될 것이고, 결국 return 되는 solve(1)의 값이 정답이 된다.
Q2. 2293 동전 1 > 문제 링크
단계1) 먼저 1원만을 사용한다면, 1원~10원을 만드는 방법은 전부 1원을 사용하는 단 한가지의 경우이다.
| idx | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1원 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
단계2) 그리고 1원과 2원을 모두 쓰는 경우를 테이블에 추가해보면 아래와 같은 형태가 되는데,
| idx | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1원 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1원+2원 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 6 |
0원은 동전을 모두 쓰지 않고 만드는 경우 1가지, 1원은 1원 하나를 쓰는 경우 한가지지만, 2원부터는 1원+1원, 2원의 경우로 나눠지게 된다.
그리고 3원을 만드는 경우, 1+1+1원, 1+2원의 두 가지이다.
그리고 4원을 만드는 경우, 1+1+1+1원, 1+1+2원, 2+2원의 3가지이다.
지금 살펴보고 있는 단계2는, 단계1에서 만들 수 있는 경우의 수에 2를 통해서 만드는 방법을 추가한 경우다.
그러므로 2는 기본적으로 하나가 추가 된다고 생각하여 , 3원에서 2원을 빼면 1원이고, 1원+2원으로 1원을 만드는 경우의 수는 한 가지이므로 총 3원을 만들어내는 경우의 수는 단계1의 수(1) + 단계2에서 추가된 수(1) 을 해서 총 2가지이다.
4원도 살펴보면, 2는 기본적으로 하나가 추가 된다고 생각하여 , 4원에서 2원을 빼면 2원이고, 1원+2원으로 2원을 만드는 경우의 수는 두 가지이므로 총 4원을 만들어내는 경우의 수는 단계1의 수(1) + 단계2에서 추가된 수(2) 을 해서 총 3가지이다.
결국 새로 만들어지는 dp[n]의 값은 이전 dp[n]값 + dp[n-현재 추가된 동전의 종류 크기]를 더한 값이라는 점을 알 수 있다.
이를 바탕으로 1원, 2원, 5원을 모두 이용하는 경우까지 추가해보면
| idx | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1원 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1원+2원 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 6 |
| 1원+2원+5원 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 |
이러한 형태가 되고, 최종적으로 1원, 2원, 5원으로 10원을 만드는 경우의 수는 10가지가 된다.
그래서 점화식은 이전 dp[n]값 + dp[n-현재 추가된 동전의 종류 크기]이므로 최종적으로 dp[j] += dp[j - arr[i]]의 형태로 구현이 되고, 이를 바탕으로 코드를 구현해보면 아래와 같다.
#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(NULL);
int n, m;
int v[101];
int dp[10001] = { 0, };
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> v[i];
}
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = v[i]; j <= m; j++) {
dp[j] += dp[j - v[i]];
}
}
cout << dp[m];
}배열 형태로 동전의 값들을 입력받고,
0원을 만드는 경우의 수는 1가지이므로 dp[0]은 1로 초기화한다.
그리고 앞서 말한 점화식을 이중 for문으로 구현하여 dp표를 채워나간다.
최종적으로 원했던 값을 인덱스로 갖는 dp테이블 값을 반환하면서 문제가 종료된다.
