[JAVA] 7579 앱

안녕하세요.

오늘의 문제는 7579번 앱입니다. 

 

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

7579번: 앱

 

사실 더 빨리 포스팅을 했어야 했는데, 주말에는 이리저리 바빠서 월요일에 올리게 됐습니다. 백수라도 주말을 챙기고 싶은 이 심보는 무엇일까요

 

아무튼 시작하겠습니다. 

 

<나의 풀이>

 

처음에는 굉장히 헤맸습니다. 

이런 저런 방법을 생각하다 보니 , 떠오르는 문제가 있었습니다. 

 

바로 첫 포스팅인 평범한 배낭 문제였습니다( https://hardworking-sloth.tistory.com/2 )

12865 평범한 배낭

 

이 문제도 최소(혹은 최대)의 상황을 구해야 하는 문제로 모든 경우를 다 확인해줘야 하는 문제입니다.  

어떻게 효율적으로 확인할까 가 문제의 해결포인트입니다. 

 

저는 평범한 배낭의 경험을 살려 메모지에이션을 사용하기로 했습니다. 물론 경험을 되살리는 것도 쉽지 않았습니다. 

 

무엇을 저장할 것인지 생각하기 쉽지 않았지만 조건을 보고 확신했습니다.

조건 중 앱 비활성 비용(단위 초)이 0~100이고 N 또한 1~100이라 배열로 충분히 만들 수 있다고 생각했습니다.

 

memo [i][j] = x 

i = i 번째 이하의 물건을 사용한다

j = j초가 주어졌때 

x = 사용가능한 메모리

 

그리고 역시나 점화식을 세워보았습니다.

 

memo [i][j] = Math.max(memo [i-1][j] , memo [i-1][j-times [i]] + memorys [i] )

times [i] = i번째 앱의 비활성 시간

memory [i] = i번째 앱의 메모리

 

마지막으로 디테일한 조건 (degenerate?)만 좀 생각해 보았습니다.

 

1) memo [0]을 미리 채워줘야 한다.

2) M(문제에서 필요한 메모리)를 만족할 때마다 갱신해줘야 한다.

3) j(현재 주어진 초)가 time [i] 보다 클 때 점화식을 사용해야 한다.

 

<코드>

import java.io.*;
import java.util.StringTokenizer;

public class Num7579 {
    static int[] memory, times;
    static int answer,m,n;
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        makeToken(bf.readLine());
        n = Integer.parseInt(st.nextToken());
        memory = new int[n];
        times = new int[n];
        m = Integer.parseInt(st.nextToken());
        makeToken(bf.readLine());
        for(int i=0;i<n;i++){
            memory[i] = Integer.parseInt(st.nextToken());
        }
        makeToken(bf.readLine());
        for(int i=0;i<n; i++){
            times[i] = Integer.parseInt(st.nextToken());
        }
        answer = Integer.MAX_VALUE;
        dp();
        System.out.println(answer);

    }
    //이런거 메소드 만들어보기 
    public static void makeToken(String input){
        st = new StringTokenizer(input," ");
    }
    public static void dp() {
        int[][] memo = new int[n][10001];
        for(int i=0;i<10001;i++){
            if(i>=times[0]){
                memo[0][i] = memory[0];
            }
            // 1번째 물건도 비교가 필요
            if(m<=memo[0][i]){
                answer = Math.min(i,answer);
            }
        }
        for(int i=1;i<n;i++){
            for(int j=0;j<10001;j++){
                memo[i][j] = memo[i-1][j];
                if(j>=times[i]){
                    memo[i][j] = Math.max(memo[i][j], memo[i-1][j- times[i]]+ memory[i]);
                }
                if(m<=memo[i][j]){
                    answer = Math.min(j,answer);
                }

            }
        }
    }
}

 

<후기>

1. 문제가 안 풀릴 때, 문제의 출처를 보지 말자 보통 초중고 문제라 속상해짐 ㅜ

2. 꼼꼼하게 생각하기 ( ex memo 배열을 10001이 아닌 5050으로 했음 갑자기 분위기 가우스 ) 

3. 맞춤법 검사 꼭 하자