기록하지 않았다면 잃어버릴 시간들
Home
  • 분류 전체보기 (184)
    • Lang (6)
      • c++ (2)
      • Java (2)
      • python (2)
    • 프레임워크 (18)
      • Spring (16)
      • JPA (2)
    • 알고리즘 (141)
      • 이론 (4)
      • 백준 (59)
      • Codility (13)
      • 프로그래머스 (65)
    • CS (4)
      • 운영체제 (0)
      • 자료구조 (0)
      • DB (4)
      • 네트워크 (0)
      • 보안 (0)
    • 기타 (7)
    • 프로젝트 (4)
      • 게시판 만들기로 배우는 Spring Data JP.. (4)
Home
  • 분류 전체보기 (184)
    • Lang (6)
      • c++ (2)
      • Java (2)
      • python (2)
    • 프레임워크 (18)
      • Spring (16)
      • JPA (2)
    • 알고리즘 (141)
      • 이론 (4)
      • 백준 (59)
      • Codility (13)
      • 프로그래머스 (65)
    • CS (4)
      • 운영체제 (0)
      • 자료구조 (0)
      • DB (4)
      • 네트워크 (0)
      • 보안 (0)
    • 기타 (7)
    • 프로젝트 (4)
      • 게시판 만들기로 배우는 Spring Data JP.. (4)
블로그 내 검색

기록하지 않았다면 잃어버릴 시간들

새로운 것을 배우는게 즐거운 개발자입니다.

  • 알고리즘/백준

    BOJ 7579 앱 / C++

    2022. 7. 27.

    by. 내이름은 킹햄찌

    https://www.acmicpc.net/problem/7579

     

    7579번: 앱

    입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활

    www.acmicpc.net

    백준 온라인저지 7579번 앱 문제입니다.

     

    아이디어

    메모리를 확보하기 위해 앱을 비활성화 시키는 촤소 비용을 찾기 위한 점화식을 찾는 것이 문제의 핵심이 됩니다.

    knapsack 문제 유형인데요, 비용에 따른 최대 메모리를 찾아내면 됩니다.

    #include<iostream>
    #define MAX 100
    #define COST_MAX 10004
    using namespace std;
    
    int appInfo[2][MAX];
    int dp[COST_MAX];
    int n, m;
    
    int max(int a, int b) {
    	return a > b ? a : b;
    }
    
    void input() {
    	cin >> n >> m;
    	for (int i = 0; i < n; i++) 
    		cin >> appInfo[1][i];
    	
    	
    	for (int i = 0; i < n; i++) 
    		cin >> appInfo[0][i];
    	
    	
    }
    
    void solution() {
    	for (int i = 0; i < n; i++) {
    		for (int j = COST_MAX - 1; j >= appInfo[0][i]; j--) {
    			dp[j] = max(dp[j], dp[j - appInfo[0][i]] + appInfo[1][i]);
    		}
    	}
    	for (int i = 0; i < COST_MAX; i++) {
    		if (dp[i] >= m) {
    			cout << i;
    			return;
    		}
    	}
    
    }
    int main(void) {
    	input();
    	solution();
    }

    '알고리즘 > 백준' 카테고리의 다른 글

    BOJ 12100 2048(Easy) / C++  (0) 2022.07.31
    BOJ 14891 톱니바퀴 / C++  (0) 2022.07.27
    BOJ 2933 미네랄 / C++  (0) 2022.07.26
    BOJ 1966 프린터 큐 / C++  (0) 2022.07.26
    BOJ 3190 뱀 / C++  (0) 2022.07.26

    댓글

    관련글

    • BOJ 12100 2048(Easy) / C++ 2022.07.31
    • BOJ 14891 톱니바퀴 / C++ 2022.07.27
    • BOJ 2933 미네랄 / C++ 2022.07.26
    • BOJ 1966 프린터 큐 / C++ 2022.07.26
    맨 위로
전체 글 보기
Tistory 로그인
Tistory 로그아웃
로그아웃 글쓰기 관리

Today

Total

Powered by ⓒ Kakao Corp.

Designed by Nana
블로그 이미지
내이름은 킹햄찌

티스토리툴바