백준 dynamic programming 7579 번

혹시 누군가 백준 알고리즘을 풀다 이것을 보게된다면 다른 사람의 블로그를 봐주세요..

완전한 스터디 목적이므로 쫌 조잡한 부분이 많습니다

중간중간 계속 다른곳으로 새기 때문에 깔끔하게 풀이를 보고싶은분은 다른 블로그를 참고하길

*중간에 헤맨것 까지 다 나와있으므로 그냥 따라해서는 안됩니다..

뻘짓 포함

7579 문제

우선 c++로 split하는 방법 ->사실 이게 필요 없었음..그래도 언젠가는 도움될 자료니까

나는 역시 자바가 편하긴하다..자바는 split함수 하나면 되는데..

1. string 배열 선언후, 배열로 입력받고 처리 
2. split함수 직접 구현 (공백 단위로 문자 잘라서 vector에 넣음)
3. std::istream_iterator<std::string>(iss) 사용

우선 이렇게 있다고 함

그래도 c++쓰는거니까 라이브러리를 사용해 보도록 하겠다

(직접 구현하는건 나중에 공백말고 다른 구분자로 구분해야할대 사용해보도록 하겠음)

 

오잉 그냥 strtok쓸래

-문자열을 strtok를 사용해 공백을 기준으로 자르고 배열에 넣는것을 우선 해봄

이거 사용해서 하면 될듯

 

문자열을 공백으로 자르고 배열에 넣어 출력한것

*또 다른 방법

입력받을 갯수가 정해져있다면 이걸 쓰는게 더 간단함

근데 사실 우리는 이런식으로 첫줄을 받아도 상관은 없을듯 받을 갯수가 정해져있으니까

M이랑 n만 따로 받아도 되는데 어차피 2번째 줄부터는 문자열을 공백으로 나눠야하니까 우선 통일해서 사용하도록 하겠음

 

//또다른 난관 ㅎㅎ 입력받는걸 생각안함

getline을 사용해서 받을건데 그이유는 공백까지 읽어야 하기 때문

보통 cin으로 그냥 읽으면 공백에서 끊겨버림

이걸 사용해 풀어보도록 하겠음!!

 

int main(void) {
int i = 0;
int n;
int m;
char *context; //이건 strtok_s쓰려고 그냥 쓰는거
char str_num[10] = {0};//M의 범위가 100000000이므로 총문자가 8개니까 10으로 잡음
cin.getline(str_num, 10); //괄호 안에는 문자열을 저장할 char배열명,저장할 문자의 최대 개수를 쓴다.

char* tok_nm[3] = {};
char *tok = strtok_s(str_num, " ", &context);
while (tok != NULL) {
tok_nm[i] = tok;
i++;
tok = strtok_s(NULL, " ", &context);
}
//첫줄 나누기 끝

n = atoi(tok_nm[0]);
m = atoi(tok_nm[1]);
//n,m 할당 끝 


return 0;

//이것보다 간단한게 있어서 바꿈!이건 그냥 나중에  strtok_s사용할일 있을때 참고자료로 봐야겠다.

 

//점화식

1.우선 M을 넘을때 cost저장하고

2.i였으면 i+1도 넣어서 m넘는 경우에 cost를 이전 cost와 비교해 더 작은걸 저장한다.

=>단순하게 탐색하면 time limit에 걸리겠지

이래서 dynamic programming을 이용해야 한다고 한다..왜 여기에 이용하는건지..알고리즘 공부좀 더해야지

dp[메모리] = cost(최소값)이라고 생각을 했엇음

하지만 !!

dp[cost]=memory(최대값) 이런식으로 할당을 하면 범위가 줄어들겠지=>memory는 60만 넘으면 되니까!!값이 정해져있다고 해야하나 

=>어떤 cost에 들어갈수 있는 최대 메모리적재량을 구하면됨

1. 입력받은 cost를 다 더함 ->cost0부터 그 값까지의 cost에 대한 최대 메모리 적재량을 구하면 되니까

//이것도 괜찮고 아예 0부터 하나하나 더해가면서 범위를 지정 Ex)0부터 15까지 비교 이런식으로 해도됨_->근데 이건 다시 또 비교해줘야 하고 값을 저장하는게 귀찮..

 

2. 나중에는 0부터 1)의 cost까지에서 m을 넘는게 있으면 출력하면 됨=>어차피 Cost는 작은것부터 비교하니까 M 넘는거 있으면 출력하면 됨

 

#include <iostream>
#include <string.h>
#include <algorithm> //이것때문에 max함수 사용 가능
#define MAX 101

using std::cout;
using std::endl;
using std::cin;
using std::max;

int n;
int m;
int memory[MAX] = { 0 };
int cost[MAX] = { 0 };
int total_memory = 0;
int total_cost = 0;
int result = 0;
int dp[10001] = {0};
bool flag = false;

int main(void) {
int arr_num = 0;
int j;
cin >> n >> m;

for (int i = 0;i < n;i++) {
cin >> memory[i];
}
for (int i = 0;i < n;i++) {
cin >> cost[i];
total_cost += cost[i];
}

for (int i = 0;i < n;i++) {
for (j = total_cost;j >= cost[i];j--) {        //j=total_cost라는 건 모든 어플이 비활성화 되어있는 상태
dp[j] = max(dp[j], dp[j - cost[i]] + memory[i]);//i번째를 활성화 하므로 i번째 어플의 메모리를 더함
}
}

for(int i=0;i<total_cost;i++){
if (dp[i] >= m) {
result = i;
break;
}
}
cout << result << endl;


return 0;
}

 

드디어! 풀.었.다