카라멜마끼아또

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

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/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]);
    }