#include <iostream>
#include <algorithm>
using namespace std;
//dp[i][j]= 처음부터 i번째 까지의 물건을 살펴보고, 배낭의 용량이 j였을 떄 배낭에 들어간 물건의 가치합의 최댓값
//예를 들어
int dp[101][100001];
int W[101];
int V[101];
int main() {
//N은 물건의 갯수를 의마한다.
//K는 버틸수 있는 물건의 무게를 의미한다.
int N, K;
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> W[i] >> V[i];
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= K; j++) {
if (j - W[i] >= 0) {
//현재 무게의 최댓갑은 이전아이템까지 넣은 단계에서의 최댓값과
//지금 아이템의 무게를 넣은 물건의 값을 비교하여 더 큰값을 넣는다.
//i번째 물건을 넣을 지 말지가 중요하다.
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]]+V[i]);
}
else {
//현재 아이템을 넣었을때 무게가 오바된다면 넣지 않고 이전걸 그대로 가져온다
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[N][K];
}
코드를 살펴보면 일다 우리는 가지고 있는 첫번째 아이템 부터 차근차근 가방에 넣을 것이다. 차근차근 넣을 때 제한 무게를 초과한다면 그 아이템은 넣지 않는다가 이문제의 핵심이다. 즉 i번째 아이템을 넣은 것과 안 넣은 것의 최댓값을 계속 갱신해주면서 진행하는게 해당 문제의 해결 방법이다. i=1일때 우리는 가방에 이 아이템을 넣을지 말지 결정 한다. dp[0][0]은 어차피 0이다 하지만 무게해당하는 j값이 0이기에 일단 넣지 않는다. 이에 dp[1][6]=13이다 즉 1번아이템을 넣었을 때의 무게는 6이고 13이다라는 의미이다 이제 2번아이템을 넣는다고 가정해보자 2번아이템도 마찬가지로 진행이된다. dp[4][4]의 가치는 일단 8이다 하지만 이제 dp[6]으로 간다면 2번까지 넣어서 6이하의 무게를 만든 가방보다 1번만 넣어서 6이하의 무게를 가진 가방의 가치가 더높으므로 dp[2][6]=13이다.
자이제 3번아이템까지 넣는다고 가정하자 일단 dp[3][3]=6이다 dp[2][4]=8이고 이에 따라 dp[3][4]=8이다
dp[3][7]의 기준으로 보자 지금 까지는 dp[1][6]의 값이 계속 들어 와서 13이었을 것이다. 하지만 3번 아이템을 넣는다고 가정해보았을 때 dp[2][4]+dp[3][3] 즉 dp[2][4]+V[i]의 값이 기존의 dp[2][7]즉 dp[1][6]의 값이 계속 넣어진 상황 보다 큼으로
일단 위 코드의 이부분은 pair로 이루어진 큐에서 값을 뽑고 그값을 기준으로 상하좌우의 값을 큐에다가 다시 넣어준다 그후 넣어준큐의 순서에대한 값이 저장되어있는 answer배열에 나의 방문번째수 +1을 넣어서 해준다 즉 내가 2번 layer에 자식이라면 나의 상하좌우는 3번 layer 에 자식이된다
트리로 그리게 되면 이런 구조가 된다. 그후 내가 몇번째 layer에 있는지를 answer배열에 저장해주면 된다.
이 문제는 일단 백준상에서 골드 5로 되어있는 문제다 근데 이문제를 보았을 때 느낀게 과연 내가 이 문제가 백트래킹인걸 모르고 풀었을 때 빠르게 정답을 유추 할 수 있었을까? 절대 아니다. 요즘 해당 알고리즘이 주어질 경우에는 그 알고리즘으로 문제를 빠르게 풀지만 내가 어떤 문젠지를 모르면 풀 수 있을 지는 모르겠다. 확실히 실무를 보다보니 머릿속에 생각한 것을 그대로 구현하는 구현능력은 조금 올라갔는데 앞으로도 계속 좋은 일이 있었으면 좋겠
#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
char arr[16];
char answer[16];
int cnta;
int cntj;
bool isPassword;
int solution(int level, int beforeindex) {
if (level == N) {
cnta = 0;
cntj = 0;
isPassword = false;
for (int i = 0; i < N; i++) {
if (answer[i] == 'a' || answer[i] == 'e' || answer[i] == 'i' || answer[i] == 'o' || answer[i] == 'u')
{
cnta++;
}
else
cntj++;
if (cnta > 0 && cntj > 1) {
isPassword = true;
break;
}
}
if (isPassword) {
for (int i = 0; i < N; i++) {
cout << answer[i];
}
cout << endl;
}
}
else {
for (int i = beforeindex + 1; i <= M; i++) {
answer[level] = arr[i];
solution(level + 1, i);
}
}
return 0;
}
int main() {
cin >> N >> M;
for (int i = 1; i <= M; i++) {
cin >> arr[i];
}
sort(arr+1,arr+M+1);
solution(0, 0);
}
이코드의 경우 모음의 개수를 세주는 CNTA 자음의 개수를 세주는 CNTJ라는 변수가 존재 한다 이 변수의 경우 루프를 돌다가 특정 조건을 만족했을 때 바로 루프를 탈출하게 해준다. 즉 최종 4글자 가 모였을 때 이 문자열이 모음이 1개이상 자음이 2개이상이면 더이상 조건을 판단할 필요없으니 루프를 탈출하게 해주는 것이다.
else {
for (int i = beforeindex + 1; i <= M; i++) {
answer[level] = arr[i];
solution(level + 1, i);
}
}
이 부분의 경우는 재귀를 이용해서 백트래킹을 하기 위함인데 정렬되어있는 arr값에서 자기 이전의 index보다 큰 인덱스 부터 시작하기에 무조건 오름차순이 된다.
이 문제는 너무 쉽다 dp이긴 한데 점화식으로 풀었다고 하기엔 애매하다 1부터 123을 다 더해서 작으면 다시 더한후 그값이 커지면 그 이후로는 계산을 안하면 되겠다는 생각으로 이 문제를 풀었다 이문제는 생각 보다 매우 쉬웠다 설명할것도 없이 코드를 보면 이해가 될것이다
#include <iostream>
#include<queue>
using namespace std;
int T;
queue <int> n;
int answer[12];
int solution(int start,int answerindex) {
if (start == answerindex) {
answer[answerindex]++;
}
else if (start > answerindex) {
return 0;
}
else {
solution(start + 1, answerindex);
solution(start + 2, answerindex);
solution(start + 3, answerindex);
}
return 0;
}
int main() {
cin >> T;
int temp;
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for (int i = 1; i <= T; i++) {
cin >> temp;
n.push(temp);
}
while (!n.empty()) {
temp = n.front();
n.pop();
solution(0, temp);
cout << answer[temp] << endl;
}
}
