백준(Java)/23년 8월

[Java] 백준 - 7579번: 앱

C0MPAS 2023. 8. 7. 14:38

8월 7일(월) - 다이나믹 프로그래밍 (7579번)

 

7579번: 앱

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

www.acmicpc.net

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. memory 배열을 입력받을때만 st 를 새로 선언하고, cost 배열때는 빼먹었더니 NoSuchElement 오류가 발생

-> 입력을 받는 과정에서 줄이 바뀌면서 Stringtokenizer를 사용하려면,

    줄이 바뀔때마다 st = new StringTokenizer ~를 매번 작성하자

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 -> 틀렸습니다 (2023.11.19 재채점)

(C언어 풀이 활용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] memory = new int[N+1];
        int[] cost = new int[N+1];
        int[][] dp = new int[N+1][10001];

        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++)
        {
            memory[i] = Integer.parseInt(st.nextToken());
        }

        int sum = 0;
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++)
        {
            cost[i] = Integer.parseInt(st.nextToken());
            sum = sum +cost[i];
        }

        for(int i=1; i<=N; i++)
        {
            for(int j=1; j<=sum; j++)
            {
                if(j - cost[i] >= 0)
                {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-cost[i]] + memory[i]);
                }
                else
                {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        for(int i=0; i<=sum; i++)
        {
            if(dp[N][i] >= M)
            {
                System.out.println(i);
                break;
            }
        }

    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

수정 풀이 (2023.12.18)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] memory = new int[N+1];
        int[] cost = new int[N+1];
        int[][] dp = new int[N+1][10001];

        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++)
        {
            memory[i] = Integer.parseInt(st.nextToken());
        }

        int sum = 0;
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++)
        {
            cost[i] = Integer.parseInt(st.nextToken());
            sum = sum +cost[i];
        }

        for(int i=1; i<=N; i++)
        {
            for(int j=0; j<=sum; j++) // int j=1로 시작하던 풀이를 int j=0으로 수정
            {
                if(j - cost[i] >= 0)
                {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-cost[i]] + memory[i]);
                }
                else
                {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        for(int i=0; i<=sum; i++)
        {
            if(dp[N][i] >= M)
            {
                System.out.println(i);
                break;
            }
        }

    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

저작자표시