Baekjoon #16493 · Algorithm Solutions

SOLUTION INFO

Java · Main.java

작성자: tony9402
공동 작성자: 없음
링크: 제출 보기 ↗ GitHub 원본 ↗

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main {
    static public void main(String[] args) {
        FastReader rd = new FastReader();

        int N = rd.nextInt(), M = rd.nextInt();
        int []days = new int[M + 1];
        int []pages = new int[M + 1];
        for(int i = 1; i <= M; ++i) {
            days[i] = rd.nextInt();
            pages[i] = rd.nextInt();
        }

        int [][]DP = new int[N + 1][M + 1];
        int ans = 0;
        for(int k = 1; k <= M; ++k) {
            for(int i = N; i >= days[k]; --i) {
                for(int j = 1; j <= M; ++j) {
                    DP[i][j] = Math.max(DP[i][j], DP[i - days[k]][j - 1] + pages[k]);
                    ans = Math.max(ans, DP[i][j]);
                }
            }
        }

        System.out.println(ans);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
        double nextDouble() { return Double.parseDouble(next()); }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

SOLUTION DESCRIPTION

풀이 설명

DP[i][j]: i일 동안 j개의 챕터를 읽었을 때 읽은 최대 페이지 수 ```DP[i][j] = max(DP[i - days[k]][j - 1] + pages[k])``` i를 뒤에서부터 채워야 아이템을 한번씩 채울 수 있다. 앞에서부터 채운다면 챕터를 i일 동안 2번 이상 읽은걸로 채워지기 때문이다. ```cpp for k 1...M for i N...1 for j 1...M DP[i][j] = max(DP[i - days[k]][j - 1] + pages[k]) ``` 시간복잡도: O(NM^2) Quiz! 시간복잡도를 줄일 수가 있습니다. 힌트: 여기서 꼭 "j개의 챕터를 읽었을 때"를 봐야할까요?

SOLUTION INFO

Java · Main2.java

작성자: tony9402
공동 작성자: 없음
링크: 제출 보기 ↗ GitHub 원본 ↗

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main {
    static public void main(String[] args) {
        FastReader rd = new FastReader();

        int N = rd.nextInt(), M = rd.nextInt();
        int []days = new int[M + 1];
        int []pages = new int[M + 1];
        for(int i = 1; i <= M; ++i) {
            days[i] = rd.nextInt();
            pages[i] = rd.nextInt();
        }

        int []DP = new int[N + 1];
        int ans = 0;
        for(int k = 1; k <= M; ++k) {
            for(int i = N; i >= days[k]; --i) {
                DP[i] = Math.max(DP[i], DP[i - days[k]] + pages[k]);
                ans = Math.max(ans, DP[i]);
            }
        }
        System.out.println(ans);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
        double nextDouble() { return Double.parseDouble(next()); }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

SOLUTION DESCRIPTION

풀이 설명

DP[i]: i일 동안 j개의 챕터를 읽었을 때 읽은 최대 페이지 수 ```DP[i] = max(DP[i - days[k]] + pages[k])``` i를 뒤에서부터 채워야 아이템을 한번씩 채울 수 있다. 앞에서부터 채운다면 챕터를 i일 동안 2번 이상 읽은걸로 채워지기 때문이다. ```cpp for k 1...M for i N...1 DP[i] = max(DP[i - days[k]] + pages[k]) ``` 시간복잡도: O(NM) Quiz! 또 다른 디피 점화식으로 문제를 풀 수 있습니다 ! 어떻게 점화식을 세울 수 있을까요?

SOLUTION INFO

Java · Main3.java

작성자: tony9402
공동 작성자: 없음
링크: 제출 보기 ↗ GitHub 원본 ↗

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main {
    static public void main(String[] args) {
        FastReader rd = new FastReader();

        int N = rd.nextInt(), M = rd.nextInt();
        int []days = new int[M + 1];
        int []pages = new int[M + 1];
        for(int i = 1; i <= M; ++i) {
            days[i] = rd.nextInt();
            pages[i] = rd.nextInt();
        }

        int []DP = new int[6001];
        for(int i = 1; i <= 6000; ++i) {
            DP[i] = Integer.MAX_VALUE;
        }
        for(int k = 1; k <= M; ++k) {
            for(int i = 6000; i >= pages[k]; --i) {
                if(DP[i - pages[k]] == Integer.MAX_VALUE) continue;
                DP[i] = Math.min(DP[i], DP[i - pages[k]] + days[k]);
            }
        }
        int ans = 0;
        for(int i = 1; i <= 6000; ++i) {
            if(DP[i] <= N) {
                ans = i;
            }
        }
        System.out.println(ans);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
        double nextDouble() { return Double.parseDouble(next()); }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

SOLUTION DESCRIPTION

풀이 설명

DP[i]: i 페이지를 읽는데 걸린 최소 일 수 ```DP[i] = min(DP[i - pages[k]] + days[k])``` i를 뒤에서부터 채워야 아이템을 한번씩 채울 수 있다. 앞에서부터 채운다면 챕터를 i일 동안 2번 이상 읽은걸로 채워지기 때문이다. ```cpp for k 1...M for i N...1 DP[i] = max(DP[i - pages[k]] + days[k]) ``` 시간복잡도: O(6000M)

SOLUTION INFO

Java · Main4.java

작성자: tony9402
공동 작성자: 없음
링크: 제출 보기 ↗ GitHub 원본 ↗

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main {
    static public void main(String[] args) {
        FastReader rd = new FastReader();

        int N = rd.nextInt(), M = rd.nextInt();
        int [][]DP = new int[N + 1][M + 1];

        int ans = 0;
        for(int k = 1; k <= M; ++k) {
            int day = rd.nextInt();
            int page = rd.nextInt();
            for(int i = day; i <= N; ++i) {
                int mx = 0;
                for(int j = 1; j < k; ++j) {
                    mx = Math.max(mx, DP[i - day][j]);
                }
                DP[i][k] = mx + page;
                ans = Math.max(ans, DP[i][k]);
            }
        }
        System.out.println(ans);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
        double nextDouble() { return Double.parseDouble(next()); }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

SOLUTION DESCRIPTION

풀이 설명

DP[i][j]: i일에 j번 챕터를 다 읽었을 때 최대 페이지 수 ```DP[i][j] = max(DP[i - days[j]][1..j-1]) + pages[j]``` 시간복잡도: O(NM^2) ## Quiz! 여기서 디피 테이블을 일차원으로 바꿀수가 있습니다. 어떻게 할 수 있을까요?