데일리썽

문제 제목 : 가장 긴 증가하는 부분 수열

난이도 : 하

문제 유형 : 동적 프로그래밍(DP), LIS

추천 풀이 시간 : 30분 (못하면 2배 60분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int result = 0;
        ArrayList<Integer> a = new ArrayList<Integer>();
        int[] dp = new int[1000];
        
        for (int i = 0; i < n; i++) {
            a.add(sc.nextInt());
        }
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (a.get(i) > a.get(j)) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }  

        System.out.println(result);
    }
}

문제 제목 : 평범한 배낭

난이도 : 하

문제 유형 : 동적 프로그래밍(DP)

추천 풀이 시간 : 30분 (못하면 2배 60분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();    
        int[][] dp = new int[n + 1][k + 1];
        
        for (int i = 1; i < n + 1; i++) {
            int w = sc.nextInt();
            int v = sc.nextInt();
            
            for (int j = 1; j < k + 1; j++) {
                if (j < w) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
                }
            }
        }
        
        System.out.println(dp[n][k]);
    }
}

문제 제목 : 01타일

난이도 : 하

문제 유형 : 동적 프로그래밍(DP)

추천 풀이 시간 : 20분 (못하면 2배 40분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        long[] dp = new long[1000001];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < n + 1; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
        }  
        
        System.out.println(dp[n]);
    }
}

문제 제목 : 파도반 수열

난이도 : 하

문제 유형 : 동적 프로그래밍(DP)

추천 풀이 시간 : 20분 (못하면 2배 40분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        
        long[] dp = new long[101];
        for (int i = 1; i < 101; i++) {
            if (i <= 3) {
                dp[i] = 1;
            } else if (i <= 5) {
                dp[i] = 2;
            } else {
                dp[i] = dp[i - 1] + dp[i - 5];
            }
        }  
        
        for (int i = 0; i < t; i++) {
            int n = sc.nextInt();
            System.out.println(dp[n]);
        }
    }
}

문제 제목 : 2×n 타일링

난이도 : 하

문제 유형 : 동적 프로그래밍(DP)

추천 풀이 시간 : 20분 (못하면 2배 40분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[1001];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i < n + 1; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
        }
        
        System.out.println(dp[n]);
    }
}

문제 제목 : 프린터 큐

난이도 : 하

문제 유형 : 큐, 구현, 그리디

추천 풀이 시간 : 25분 (못하면 2배 50분)

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

import java.util.*;

class Docs {
    private int index;
    private int priority;
    
    public Docs(int index, int priority) {
        this.index = index;
        this.priority = priority;
    }
    
    public int getIndex() {
        return this.index;
    }
    
    public int getPriority() {
        return this.priority;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        int n;
        int m;
       
        for (int i = 0; i < tc; i++) {
            n = sc.nextInt();
            m = sc.nextInt();
            
            Queue<Docs> docsQueue = new LinkedList<Docs>();
            Queue<Integer> prioQueue = new PriorityQueue<Integer>();
            
            for (int j = 0; j < n; j++) {
                int priority = sc.nextInt();
                docsQueue.add(new Docs(j, priority));
                prioQueue.add(-priority);
            }
            
            int cnt = 0;
            while (true) {
                Docs docs = docsQueue.poll();
                if (docs.getPriority() >= -prioQueue.peek()) {
                    cnt++;
                    prioQueue.poll();
                
                    if (docs.getIndex() == m) {
                        System.out.println(cnt);
                        break;
                    }
                } else {
                    docsQueue.add(new Docs(docs.getIndex(), docs.getPriority()));
                }
            }
        }
    }
}

문제 제목 : 스택 수열

난이도 : 하

문제 유형 : 스택, 그리디

추천 풀이 시간 : 30분 (못하면 2배 60분)

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

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        ArrayList<Character> result = new ArrayList<>();
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        int num = 1;
        for (int i = 0; i < n; i++) {
            int data = Integer.parseInt(br.readLine());
            while (num <= data) {
                stack.push(num++);
                result.add('+');
            }
            if (stack.peek() == data) {
                stack.pop();
                result.add('-');
            } else {
                System.out.println("NO");
                return;
            }
        }
        
        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i));
        }
    }
}

문제 제목 : 블랙잭

난이도 : 하

문제 유형 : 배열, 완전 탐색

추천 풀이 시간 : 20분 (못하면 2배 40분)

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        
        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                for (int k = j + 1; k < arr.length; k++) {
                    int sum = arr[i] + arr[j] + arr[k];
                    if (sum <= m) {
                        result = Math.max(result, sum);
                    }
                }
            }
        }
        
        System.out.println(result);
    }
}