카라멜마끼아또

개인 공부를 위한 공간입니다
상업적 용도로 활용되지 않습니다

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

조건

주어진 행렬은 인접한 행렬끼리만 곱연산이 가능

풀이

n개의 행렬을 저장하고 있는 배열 input[][]

i ~ j 까지 곱연산의 최소 횟수를 저장하는 배열 dp[][]

우선 dp 배열의 값 초기화

i~i 의 곱연산 회수는 0이기 때문에 dp[i][j] = 0

i~ i+1 의 곱연산 횟수는 input[i][0] * input[i][1] * input[i+1][1]

그 외엔 Integer.MAX_VALUE 로

3중 반복문을 통해 간격, 시작점, 중간점을 탐색하며 값 삽입

i 는 간격

바로 다음 행렬의 곱연산 횟수는 위에 초기화에서 이미 설정해 주었기 때문

임의의 값 n 부터 n+2 까지의 행렬의 최소값을 구하기 위해 2부터 시작

j 는 시작점

입력값 처음부터 끝까지 탐색

k 는 중간점

시작점(j) ~ 시작점(j) + 간격(i) 의 곱연산 최소값을 구하기 위해 dp 배열에 저장되어있던 이전 값들을 활용

    public void solution11049() throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());

        int input[][] = new int[n][n];

        int dp[][] = new int[n][n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(reader.readLine());

            input[i][0] = Integer.parseInt(st.nextToken());
            input[i][1] = Integer.parseInt(st.nextToken());
        }
        

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){

                if(j==i)
                    dp[i][j]=0;
                else if(j==i+1)
                    dp[i][j] = input[i][0] * input[i][1] * input[j][1];
                else
                    dp[i][j] = Integer.MAX_VALUE;
            }
        }


        for(int i=2; i<n; i++){
            for(int j =0; j<n-i; j++){
                for(int k=j; k<j+i; k++){
                    int cnt = input[j][0] * input[k][1] * input[j+i][1];
                    dp[j][j+i] = Math.min(dp[j][j+i], dp[j][k] + dp[k+1][j+i] + cnt);
                }
            }
        }
        System.out.println(dp[0][n-1]);

    }

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

조건

1. 지도의 숫자는 해당 칸의 높이

2. 시작 지점은 (0,0) 도착 지점은 (m, n)

3. 항상 내리막길만 이용 (이전 칸의 높이보다 낮은 칸으로만)

4. 상하좌우로만 이동

이 조건을 만족하는 경로의 개수를 모두 구하는 문제

"경로의 개수" 를 구해야 하기 때문에 dfs 를 사용

재귀를 통한 깊이 우선 탐색으로 조건에 나온 현재 지점보다 낮은 경로 탐색

public class Main {
    
    static int m, n;
    static int dm[] = {1, 0, -1, 0};
    static int dn[] = {0, 1, 0, -1};
    static int dp[][];
    static int input[][];
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(reader.readLine());

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        input = new int[501][501];
        dp = new int[501][501];
        for(int i=0; i<m; i++){
            st = new StringTokenizer(reader.readLine());
            int idx = 0;
            while(st.hasMoreTokens()){
                input[i][idx] = Integer.parseInt(st.nextToken());
                dp[i][idx++] = -1;
            }
        }

        int result = dfs(0,0);

        System.out.println(result);
    }
    
    
    public static int dfs(int x, int y){
        
        if(x==m-1 || y==n-1){
            return 1;
        }

    
        if(dp[x][y] != -1){
            return dp[x][y];
        }

        dp[x][y]=0;

        for(int i=0; i<4; i++){
            int nextX = x+dm[i];
            int nextY = y+dn[i];

            if(nextX >= 0 && nextY >= 0 && nextX <m && nextY < n && input[nextX][nextY] < input[x][y]){
                dp[x][y] += dfs(nextX, nextY);
            }
        }


        return dp[x][y];
    }
}

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

T는 상담에 소요되는 시간

P 는 상담을 통해 받는 돈

조건

1. 상담은 동시에 하나

2. n+1 일부터는 이미 퇴사한 상태이기 때문에 상담 진행이 불가능

3. 상담이 끝난 후 돈을 받음 (다음날)

상향식으로 풀이

# 1일차

n=1

dp[1] = 0

1일차에는 어떤 상담도 완료되지 않았기 때문

1일차 이후 상담 가능한 날짜

int nextDay = 1 + t[1]

1일차 상담에는 3일이 소요되므로 nextDay = 1 + 3 = 4

dp[4] = max(dp[4], dp[1]+p[1])

dp[4] = (4일에 받을 수 있는 최대 금액) = (1일차 상담 3일치를 끝내고 받은 금액) = 10

# 2일차

n=2

dp[2] = 0

2일차 상담에는 5일 소요

nextDay = 2 + 5 = 7

dp[7] = max(dp[7], dp[2]+p[2])

dp[7] = 20

.....

# n일차

dp[n]=0

n일차 상담에는 t[n] 일 소요

nextDay = n + t[n]

dp[nextDay] = max(dp[nextDay], dp[n] + p[n])

** 주의

n번째 날의 상담 소요시간이 1일이라면, n+1 일에 금액을 받을 수 있으므로 dp 배열을 n+2 로 초기화

>> 1일 ~ n+1 일 까지

    public void solution15486() throws Exception{

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());

        int t[] = new int[n+2];
        int p[] = new int[n+2];
        int dp[] = new int[n+2];

        for(int i=1; i<=n; i++){
            String[] temp = reader.readLine().split(" ");
            t[i] = Integer.parseInt(temp[0]);
            p[i] = Integer.parseInt(temp[1]);
        }
        int max = -1;

        for(int i=1; i<=n+1; i++) {
            if(max < dp[i]){
                max = dp[i];
            }
            int nextDay = i+t[i];
            if(nextDay < n+2){
                dp[nextDay] = Math.max(dp[nextDay], max+p[i]);
            }
        }
        System.out.println(dp[n+1]);
    }

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

풀이

# 2x1

2x1 1개

1가지 경우의 수

# 2x2

2x1 2개

1x2 2개

2가지 경우의 수

# 2x3

3가지 경우의 수

# 2x4

5가지 경우의 수

......

점화식

dp[n] = dp[n-2] + dp[n-1] 도출 가능

    public void solution11726() throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());

        int dp[] = new int[1001];


        dp[1]=1;
        dp[2]=2;

        for(int i=3; i<=n; i++){
            dp[i] = (dp[i-1]+dp[i-2])%10007;
        }

        System.out.println(dp[n]);

    }

여기서 주의할 점 !!

dp 배열 크기를 n+1 로 잡으면 런타임 에러 (ArrayIndexOutOfBounds) 발생하기 때문에

입력의 최대값인 1000 + 1 의 길이로 최대 배열 생성 후 사용

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

풀이

경우의 수를 따져 보면

# 1

1

1개 

# 2

1+1

2

2개

# 3

1+1+1

2+1

1+2

3

4개

# 4

1+3

1+1+2

2+2

1+1+1+1

2+1+1

1+2+1

3+1

7개

4의 경우를 자세히 살펴보면

1+3

1+1+2

2+2

1+1+1+1

2+1+1

1+2+1

3+1

즉

1번째 케이스들에 +3

2번째 케이스들에 +2

3번째 케이스들에 +1

을 해준것과 동일

dp[n] = dp[n-3] + dp[n-2] + dp[n-1]

이라는 점화식 도출

    public void solution9095() throws Exception{

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());
        int input[] = new int[n];
        int dp[] = new int[12];
        for(int i=0; i<n; i++)
            input[i] = Integer.parseInt(reader.readLine());

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for(int i=4; i<=11; i++)
            dp[i] = dp[i-3]+dp[i-2]+dp[i-1];

        for(int i : input)
            System.out.println(dp[i]);
    }

경우의 수를 구하고자 하는 숫자의 최대값이 11이기 때문에 dp 배열의 길이를 12로 선언

dp[1] ~ dp[3] 까진 1, 2, 4 의 값을 넣어주고

4번째 케이스부터 앞선 3개의 값을 더해서 값 저장

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

풀이

문제에 나타난 조건 2개

1. 계단은 한 번에 1칸 혹은 2칸 이동 가능

2. 3칸 연속으로 밟기 불가능

2개의 조건을 만족하며 N 번째 계단을 밟기 위해서

1. N-3 을 밟고 N-2 를 건너 뛰고 N-1, N 밟기

2..N-2 를 밟고 N-1 을 건너뛰고 N 밟기

이렇게 두 가지 경우가 존재 >> 연속 3개의 계단은 못밟기 때문

따라서 위 2가지의 값 중 큰 값 + N 번째 계단의 점수를 더한 값이 N 번째 계단의 점수 최대값

각 계단의 점수를 저장하고 있는 input 배열

N번째 계단의 최대점수를 기록하는 dp

dp[N] = Max(dp[N-2], dp[N-3]+input[N-1]) + input[N]

라는 점화식 도출

    public void solution2579() throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());


        int input[] = new int[n+1];
        int dp[] = new int[n+1];

        for(int i = 1; i<=n; i++)
            input[i] = Integer.parseInt(reader.readLine());

        dp[1] = input[1];

        if(n>=2)
            dp[2] = input[1] + input[2];


        for(int i=3; i<=n; i++)
            dp[i] = Math.max(dp[i-2], dp[i-3]+input[i-1])+input[i];

        System.out.println(dp[n]);
    }

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

풀이

이 문제같은 경우는 Time out에 집중

직관적인 로직으로 n만큼 입력받는대로 sort 하고 중간값 출력 >> 당연하게도 시간초과

시간초과 해결하기 위해서 for문으로 sort를 반복하는 방법 대신 priority queue를 사용해서 중간값을 도출

두 개의 priority queue 사용

하나는 최대힙

하나는 최소힙

왜?

그래야 내용물을 끄집어 내지 않고도 중간값 도출이 가능하니까

1. 두 우선순위 큐의 사이즈를 비교해서 같으면 최대힙에 삽입, 다르면 최소힙에 삽입

>> 입력값 개수가 짝수일 경우 작은 쪽을 중간값으로 출력해야 하기 때문에

2. 두 큐에서 우선순위가 가장 높은 원소의 값을 비교

 내림차순(최대힙) 쪽의 크기가 크면 두 값을 swap

3. 내림차순(최대힙) 에서 가장 높은 우선순위의 값을 결과 string에 저장

4. 결과값 출력

좀 더 자세하게 설명해보면

초기

[ ] [ ]

1 입력 

[1] [ ]

:: 두 큐의 사이즈가 동일하기 때문에 maxPq에 삽입

중간값 1

5 입력

[1] [5]

:: 두 큐의 사이즈가 다르기 때문에 minPq에 삽입

:: swap 안함

중간값 1

2 입력

[1 2] [5]

:: 두 큐의 사이즈가 동일하기 때문에 maxPq에 삽입

:: swap 안함

중간값 2

10 입력

[1 2] [5 10]

중간값 2

-99 입력

[-99 1 2] [5 10]

중간값 2

7 입력

[-99 1 2] [5 7 10]

중간값 2

5 입력

[-99 1 2 5] [5 7 10]

중간값 5

>> 결과값 1 1 2 2 2 2 5

** 문제에 나와있는 케이스에서는 swap의 필요성을 못느껴서 임의의 케이스를 써보면

10 입력

[10] [ ]

중간값 10

5 입력

[10] [5]

:: 여기서 maxPq.peek() > minPq.peek() 조건이 만족하기 때문에 두 값을 swap

[5] [10]

중간값 5

1입력

[1 5] [10]

중간값 5

3 입력

[1 5] [3 10]

:: 조건 만족하므로 swap

[1 3] [5 10]

중간값 3

>> 결과값 10 5 5 3

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        StringBuilder sb = new StringBuilder();

        PriorityQueue<Integer> maxPq = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> minPq = new PriorityQueue<>();


        for(int i=0; i<n; i++){

            int k = Integer.parseInt(reader.readLine());

            if(maxPq.size() > minPq.size()){
                minPq.add(k);
            }
            else{
                maxPq.add(k);
            }

            if(maxPq.size()>0 && minPq.size()>0){
                if( maxPq.peek() > minPq.peek()){
                    int temp=maxPq.poll();
                    maxPq.add(minPq.poll());
                    minPq.add(temp);
                }
            }
            sb.append(maxPq.peek()+"\n");

        }
        System.out.println(sb);