Q 15486 퇴사 2

💡 문제 요약 및 분석

[ 문제 ]

첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

[ 분석 ]

문제에 주어진 예시를 기반으로 아래와 같이 표를 만들어보았다. DP로 여러 경우의 수를 따져보면서 이익을 저장하고, 새로운 선택지의 이익이 더 높다면 새로 저장한다.

남은 날짜	얻은 이익(1st)	얻은 이익(2nd)
1	45	25
2	-	-
3	30	-
4	10	10
5	-	-
6	-	-
7	-	-

### 1st
- 1일차 상담을 한다. (남은 날짜 : 7 - 3 = 4) (얻은 이익 : 10)
- 2,3일차는 상담을 하지 못한다.
- 4일차 상담을 한다. (남은 날짜 : 4 - 1 = 3) (얻은 이익 : 10 + 20 = 30)
- 5일차 상담을 한다. (남은 날짜 : 3 - 2 = 1) (얻은 이익 : 30 + 15 = 45)
- N+1일째 되는 날에는 회사에 없기 때문에 6,7일차 상담을 하지 못한다.
최종 이익 : 45

### 2nd
- 1일차 상담을 한다. (남은 날짜 : 7 - 3 = 4) (얻은 이익 : 10)
- 4일차 상담을 건너뛴다. (남은 날짜 : 4 - 1 = 3) (얻은 이익 없음 : 10)
- 5일차 상담을 한다. (남은 날짜 : 3 - 2 = 1) (얻은 이익 : 10 + 15 = 25)
최종 이익 : 25

💡 알고리즘 설계

1. 입력

   • 표준입력 : int n
   • 표준입력 : int[][] time, int[][] pay
   • Map<Integer, Integer> memo

2. 연산

   • dp(int day, int profit) 함수 생성.
   • 1. 상담을 하지 않는다. memo.get(day - 1) 로 저장된 이익을 조회하고, 현재 이익이 더 높으면 새로 저장한다. dp(day - 1,profit) 함수 호출한다.
   • 2. 상담을 한다. memo.get(day - time) 로 저장된 이익을 조회하고, 현재 이익이 더 높으면 새로 저장한다. dp(day - time, profit + pay) 함수 호출한다.
   • day < 0 일 때 종료한다.

3. 출력

💡 코드

public class Main {

    static int n;

    static int read() throws Exception {
        int c = 0, n = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        n = read();
        backTracking(0, "");
    }

    static void backTracking(int count, String origin) {
        if (count == n) {
            System.out.println(origin);
            System.exit(0);
        }
        for (int i = 1; i <= 3; i++) {
            if (check(origin + i)) {
                backTracking(count + 1, origin + i);
            }
        }
    }

    static boolean check(String checkStr) {
        int len = checkStr.length() / 2;
        for (int i = 1; i <= len; i++) {
            if (checkStr.substring(checkStr.length() - i)
                    .equals(checkStr.substring(checkStr.length() - 2 * i, checkStr.length() - i))) {
                return false;
            }
        }
        return true;
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(3^n * n)	O(n^2)