지제로의 블로그

풀이과정 1. N, K와 N개의 동전의 가치를 입력받는다. 2. dp배열을 통해 bottom-up 방식을 이용하여 접근한다. 3. for문을 통해 dp[j] +=dp[j-money[i]]를 이용한다. (현재의 가치는 현재의 가치에서 돈을 뺀 과거의 가치를 더해주면 된다.) (과거의 값을 계속 더해줘서 현재의 가치가 업데이트된다.) #include #include using namespace std; int N,K, answer; int money[101]; int main(){ scanf("%d %d",&N,&K); vector dp(K+1); for(int i=1;i

문제 설명 이 문제에서 그나마 좋았던 점은 바로 넉넉한 시간과 넉넉한 메모리 제한이었다. 여기서 제일 중요한 점은 벽을 꼭 3개를 세워야 한다는 점이었다. 바이러스가 퍼지지 않은 빈 칸에 벽이 세워질 수 있음을 기억해야한다. 코드 #include #include using namespace std; int N,M,ans=0; int map[8][8],dx[]={-1,1,0,0}, dy[]={0,0,-1,1}; int tmp[8][8]; queueq; //void print(){ //int i,j; //for(i=0;i

이 문제는 이분탐색, 매개 변수 탐색 문제 중에서 쉬운 편이라고 생각했다. (비록 여러 번 틀렸지만..^^) 문제 설명 그대로 정해진 총액 M이하에서 가능한 최대의 총 예산을 배정하는 문제이다. 배정될 수 있는 경우엔 요청 금액을 그대로 배정하고, 그렇지 않은 경우엔 상한선을 배정한다. findLimit함수를 통해서 현재 정한 상한선(money)을 기준으로 M만큼 줄 수 있는 지 확인했다. result를 통해서 findLimit에서 참인 경우 해당 돈을 저장했다. 틀렸던 이유: left값을 처음에 입력받은 예산들 중 가장 작은 값을 넣어서 틀렸다. #include #include using namespace std; int N, M; int city[10004]; bool findLimit(int mon..