꿈을 보는 개발자

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)

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

1912번: 연속합 (acmicpc.net)

생각보다 간단했던 문제입니다. 하지만 메모리초과 부분에서 아쉬움이 있었습니다. 

n개의 정수로 이루어진 수열과 똑같은 크기의 수열을 하나 만들어서 연속해서 계속 더해줍니다. 그대신 연속해서 더한 수와 더하지 않고 그 자리에 있는 수만 더할 경우 두가지의 경우중 큰 경우를 새로 만들어준 배열에 저장하고 그 후, 그 배열중 최대값을 출력합니다.

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());
        int number[] = new int[t];
        int sum[] = new int[t];
        int result = Integer.MIN_VALUE;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < t; i++) {
            number[i] = Integer.parseInt(st.nextToken());
            sum[i] = Integer.MIN_VALUE;
        }

        for (int i = 0; i < t; i++) {
            if (i == 0) {
                sum[i] = number[i];
            } else {
                sum[i] = Math.max(sum[i - 1] + number[i], number[i]);
            }
            if(result < sum[i]){result = sum[i];}

        }


        System.out.println(result);
    }
}

부족했던 점

처음에 제출한 답안은 메모리초과가 발생하였습니다. 조금 더 효율적인 코드를 작성하도록 해야합니다. 

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());
        int number [] = new int[t];
        int sum[][] = new int[t][t];
        int max = Integer.MIN_VALUE;

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

        for(int i = 0; i<t; i++){
            for(int j=i; j<t; j++){
                if(j == 0){ sum[i][j] = number[i]; }
                else{
                    sum[i][j] = sum[i][j-1]+number[j];
                }
                if(max < sum[i][j]){max = sum[i][j];}
            }
        }
        System.out.println(max);
    }
}