꿈을 보는 개발자

11052번: 카드 구매하기 (acmicpc.net)

카드 구매하기 입니다. 문제에서는 최대한 비싼 가격으로 카드를 구매해야하기 아래의 배열부터 올라와서 높은 값을 갱신해 주어야 합니다. 따라서 아래에서 부터 최대값을 갱신해주어야 합니다. 

package com.company;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {



    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int t = Integer.parseInt(br.readLine());
        long dp[] = new long[t+1];
        long number[] = new long[t+1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i<=t; i++){
            number[i] = Integer.parseInt(st.nextToken());
        }

        for(int i =1; i<=t; i++){
            for(int j = 1; j<=i; j++){
                dp[i] = Math.max(dp[i], dp[i-j] + number[j]);
            }
        }
        System.out.println(dp[t]);
    }
}

부족했던 점

처음에는 다음과 같은 점화식을 사요했습니다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {



    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int t = Integer.parseInt(br.readLine());
        long dp[] = new long[t+1];
        long number[] = new long[t+1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i<=t; i++){
            number[i] = Integer.parseInt(st.nextToken());
        }

        dp[1] = number[1];
        if(t>1){ dp[2] = Math.max(number[2],dp[1]*2);}
        if(t>2){dp[3] = Math.max(number[3], number[1] +dp[2]);}
        for(int i =4; i<=t; i++){
                dp[i] = Math.max(number[i], Math.max(dp[i-1]+number[1], dp[i-2]+dp[2]));
        }
        System.out.println(dp[t]);
    }
}

하지만 코드는

1 100 160 1 1 1 1 1 1 1 의 반례가 존재하였습니다. 

해당 케이스의 답은 520이 나와야 하지만 제가 구성한 위의 코드는 최대값이 500이 나왔습니다. 

2225번: 합분해 (acmicpc.net)

합분해 문제입니다. 우선 합분해를 구하기 위해서 이중배열을 선언해주었습니다. 이유는 Bottom-up방식을 통해서 값을 하나씩 갱신해 나갈것인데 이를 위해서 N의 합인 수와 K개의 정수인 경우의수를 각각 나누어주어야 하기 때문입니다. 

따라서 다음과 같은 코드를 작성했습니다. 

package com.company;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {



    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        long dp[][] = new long[k+1][n+1];

        for(int i = 1; i<=k; i++){
            for(int j = 0; j<=n; j++){
                if(i == 1){dp[i][j] = 1;}
                for(int l = 0; l<=j; l++){
                    dp[i][j] +=dp[i-1][l];
                }
                dp[i][j] %= 1000000000;
            }
        }

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

부족했던 점

2차원 배열을 선언해야 한다는 점까지는 생각했지만 값을 갱신하는 방법 특히, 삼중 반복문을 사용하는 부분에서 어려움을 겪었습니다. 

9461번: 파도반 수열 (acmicpc.net)

파도반 수열입니다. 1,1,1,2,2,3,4,5,7,9의 형태로 수열이 진행됨을 알 수 있고 이를 점화식으로 표현한다면, 

F(n) = F(n-3) + F(n-2)의 점화식이 나옴을 알 수 있습니다. 이를 Bottom-up 방식으로 풀어내면 다음과 같습니다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Main {

    static long dp[]= new long [101];


    public static long padovan(int n){
        if (n == 1 || n == 2 || n == 3) {
            return 1;
        }
        else if(dp[n] == 0){
            for(int i = 4; i<=n; i++){
                dp[i] = dp[i-3] +dp[i-2];
            }
            return dp[n];
        }
        else{
            return dp[n];
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1;

        for(int i = 0; i<t; i++){
            int n = Integer.parseInt(br.readLine());
            System.out.println(padovan(n));
        }
    }
}

 시간초과를 방지하기 위해서 비어있는 배열이 아닌경우에는 바로 배열값을 반환하도록 해주었습니다. 또한 결과값이 커지기 때문에 long타입 배열을 선언 해 주었습니다. 

2133번: 타일 채우기 (acmicpc.net)

package com.company;

import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Main {


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        int dp[] = new int[t];

        if(t>2 && t%2==0){

            for(int i = 4; i<t; i++){
                dp[i] = 3*dp[i-2];
                for(int j=0;j<i-2;j+=2) { 
                    dp[i]+=dp[j] * 2; 
                }
            }
        }
        else{
            System.out.println(0);
        }

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

부족했던 점 

점화식을 찾는데 집중해야 했지만 홀수일 경우 0이되고 그 외의 요소간관계를 찾는데 어려움을 겪었습니다. 

1699번: 제곱수의 합 (acmicpc.net)

본 문제는 제곱수의 합만으로 이루어진 숫자의 최소값을 구하는 문제입니다. 가장 적은 제곱수의 합으로 나타내기 위해서는 가장 숫자가 큰 제곱수로 본 숫자를 먼저 빼고 난 후 숫자를 제곱수의 합으로 구하는 것도 있지만, 자칫하면 반례가 있을수도 있기 때문에 아래에서 부터 제곱수의 합으로 이루어진 숫자의 최소값을 갱신하는 방식을 선택 하였습니다. 

package com.company;

import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Main {


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        int dp[] = new int[t+1];

        for(int i = 1; i<=t; i++){
            dp[i] = i;
            for(int j = 1; j*j<=i; j++){
                dp[i] = Math.min(dp[i],dp[i-j*j]+1);
            }
        }

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

2579번: 계단 오르기 (acmicpc.net)

계단오르기 문제입니다. 이 문제는 이전에 풀었던 포도주 문제와 유사했던 문제였습니다. 

1,2,3번째 일경우에는 계단 오르기 규칙에 맞게 풀면되었고 나머지 경우에는 무조건 마지막 계단수를 밟아야 한다는 규칙에 따르도록 마지막 계단 + 마지막 전 계단 + 마지막 계단 -3 계단 수의 최대값을 구한 값 혹은 마지막 계단 + 마지막 계단 + 마지막 계단 -2 위치에서의 최대값 둘중 더 큰 값을 구해나가면 됩니다. 

package com.company;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        int number[] = new int[t];
        int dp[] = new int[t];


        for (int i = 0; i < t; i++) {
            number[i] = Integer.parseInt(br.readLine());
        }


        dp[0] = number[0];
        if(t>1){ dp[1] = number[0]+ number[1];}
        if(t>2){dp[2] = Math.max(number[0],number[1]) + number[2];}
        for(int i=3; i<t; i++){
            dp[i] = Math.max(dp[i-2] +number[i] ,dp[i-3] + number[i]+number[i-1]);
        }
        System.out.println(dp[t-1]);
    }
}

DP - 2156(포도주 시식) :: 꿈을 보는 개발자 (tistory.com)

해당 문제와 연계해서 풀어도 좋은 문제입니다.