꿈을 보는 개발자

11054번: 가장 긴 바이토닉 부분 수열 (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());

        int number [] = new int[t];
        int dp[] = new int[t];
        int dp2[] = new int[t];
        int max = 0;

        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++){
            dp[i] = 1;

            for(int j = 0; j<i; j++){
                    if(number[i] > number[j] && dp[i] < dp[j] + 1 ){
                        dp[i] = dp[j] + 1 ; // 증가하는 배열 검사
                    }

                }

        }

        for(int i = t -1; i>=0; i--){

            dp2[i] = 1;
            for(int j = t -1; j > i; j--){
                if(number[j] < number[i] && dp2[i] < dp2[j] + 1){
                    dp2[i] = dp2[j] + 1 ; // 역순으로 검사
                }
            }
        }

        for(int i = 0; i<t; i++){
            if(max < dp[i]+dp2[i])
            max = dp[i]+ dp2[i];
        }

        System.out.println(max -1);

    }
}

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)

11055번: 가장 큰 증가 부분 수열 (acmicpc.net)

11722번: 가장 긴 감소하는 부분 수열 (acmicpc.net)

비슷한 맥락의 문제였기 때문에 한꺼번에 포스팅 하겠습니다. 

가장 긴 증가하는 부분 수열을 구하기 위해서는 해당 하는 위치에서 맨 처음값부터 하나씩 올라와 현재 위치하는 값보다 작은지 큰가를 하나하나 비교해나갔습니다. 그리고 만약 증가하는 모양새, 즉 이전 현재 값보다 이전에 작은 수가 있다면 수열 A와 크기가 똑같은 배열하나에 1을 더해주어서 값을 갱신해 주도록 하였습니다. 이때 수열 길이를 증가하는 배열은 무조건 1로 초기화해 주었습니다. 

수열 A의 처음부터 내려오면서 이전값보다 현재 값이 크다면 증가 부분 수열을 저장하는 배열에 1을 더해줍니다. 이때, 해당 숫자와 같은 인덱스의 증가 부분 수열의 값에다가 1을 더해주어야 연속되는 배열의 증가를 알아 낼 수 있습니다.

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 dp[] = new int[t];

        int max = 0;
        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++){
            dp[i] = 1;
            for(int j = 0; j<i; j++){
                if(number[i] > number[j] && dp[i] < dp[j]+1){
                    dp[i] = dp[j] + 1 ;
                }

            }
            
            if(max < dp[i]){
                max = dp[i];
            }
        }

        System.out.println(max);

    }
}

11053코드

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 dp[] = new int[t];

        int max = 0;
        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++){
            dp[i] = number[i];
            for(int j = 0; j<i; j++){
                if(number[i] > number[j] && dp[i] < dp[j] + number[i]){
                    dp[i] = dp[j] + number[i] ;
                }
            }
            if(max < dp[i]){
                max = dp[i];
            }
        }

        System.out.println(max);

    }
}

11055 문제 같은 경우에는 11053 문제의 코드와 같은 맥락입니다. 하짐나, 증가하는 수열의 길이의 최대가 아닌 값의 최대를 구해야 하기 때문에 길이를 1더해주는 대신 수의 값을 더해주어서 값중 최대값을 출력해주도록 변경하였습니다. 

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 dp[] = new int[t];

        int max = 0;
        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++){
            dp[i] = 1;
            for(int j = 0; j<i; j++){
                if(number[i] < number[j] && dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1 ;
                }
            }
            if(max < dp[i]){
                max = dp[i];
            }
        }

        System.out.println(max);

    }
}

11722 같은 경우는 이중 11053의 조건을 하나만 바꾸어주어서 해결 했습니다. 

2156번: 포도주 시식 (acmicpc.net)

3번 연속으로 포도주를 마시면 안되기 때문에 나올 수 있는 패턴은 총 세가지가 있습니다. 

이 세가지 패턴을 가지고 패턴의 최대값을 갱신해 나간다면 문제를 해결 할 수 있었습니다. 

package com.company;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.Math;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        int wine[] = new int[t+1];
        int drink[] = new int[t+1];
        for(int i = 1; i<=t; i++){// 테스트 케이스 시도 횟수
                int temp = Integer.parseInt(br.readLine());
                wine[i] = temp;
        }

        drink[1] = wine[1];

        if(t>1){ drink[2] = wine[2]+wine[1];}

        for(int j = 3; j<=t; j++){
            drink[j] = Math.max(drink[j-2]+wine[j], Math.max(drink[j-1] , drink[j-3] + wine[j-1]+wine[j]));
        }


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

부족했던 점

시간을 오래써도 파악이 되지 않아서 다른 코드를 참고 하였습니다. 위의 패턴파악은 했지만 어떻게 구현 할까 고민했는데 점화식 파악에 조금더 익숙해져야 할 것 같습니다. 

9465번: 스티커 (acmicpc.net)

스티커 문제입니다. 2열로 제한 되어 있기 때문에 일정한 패턴을 보였습니다.

위와 같이 왼쪽 위의 스티커를 떼어낸다면 다음 스티커는 아래열의 대각선 혹은 대각선 오른쪽의 스티커 둘 중 하나를 떼어내어야만 최대 점수를 가질 수 있는 스티커를 떼어낼 수 있습니다. 이후 스티커를 하나씩 떼어낼때 마다 열을 바꾸어가면서 스티커를 떼어내야 합니다. 

이 조건을 가지고 코드를 구현한다면 다음과 같이 나오게 됩니다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.Math;
import java.util.StringTokenizer;


public class Main {




    public static void main(String[] args) throws IOException,NumberFormatException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int t = Integer.parseInt(br.readLine());

        for(int i = 0; i<t; i++){// 테스트 케이스 시도 횟수
            int num = Integer.parseInt(br.readLine());
            int number[][] = new int[2][num+1]; // 원본 배열
            int score[][] = new int[2][num+1]; // 점수를 저장할 배열


            for(int k = 0; k<2; k++){
                st = new StringTokenizer(br.readLine());
                for(int j =1; j<=num; j++){
                    number[k][j] = Integer.parseInt(st.nextToken());
                }
            }

            score[0][1] = number[0][1];
            score[1][1] = number[1][1];

            for (int j = 2; j<=num; j++){
                score[0][j] = number[0][j] + Math.max(score[1][j-1] , score[1][j-2]);
                score[1][j] = number[1][j] + Math.max(score[0][j-1] , score[0][j-2]);
            }

            System.out.println(Math.max(score[0][num], score[1][num]));
        }

    }
}

부족했던 점

처음에는 생각이 않아서 다른 코드에서 힌트를 얻어서 풀었습니다. 열이 지속적으로 바뀌고 대각선 왼쪽 혹은 대각선 방향에서의 최대값중 하나라고 생각하였는데 이때, 값을 갱신하기 위해서 점수들의 합을 갱신할 배열의 크기를 각각 1을 더해주어서 점화식이 성립하도록 해주었습니다. 

이외에도 Scanner 가 아닌 BufferedReader가 처리속도가 더 빠르기 때문에 이 문제를 기점으로 Scanner 사용은 최대한 자제하려고 합니다. 

2193번: 이친수 (acmicpc.net)

1부터 시작해서 1이 두번 연속으로 나타나지 않는 이친수를 찾는 문제였습니다. 

• 1
• 10
• 100,101
• 1010,1001,1000
• 10101,10010,10000,10001,10000

이런식의 패턴을 볼 수 있습니다. 가지수는 1 , 1 , 2 , 3 , 5, 8 ,13의 패턴을 나타내고 이 패턴은

피보나치 수열임을 알 수 있었습니다. 간단하게 피보나치 수열만 구현한다면, 해결할 수 있었습니다. 

이번에는 Bottom-up 방식을 통해서 구현해보았습니다. 

import java.util.Scanner;

public class Main {
    static long number[] = new long[91];

    public static long cal(int num){


        number[0] = 1;
        number[1] = 1;

        for(int i=2; i<num; i++){
            number[i] = number[i-1] + number[i-2];
        }

        return number[num-1];
    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
            System.out.println(cal(n));
    }
}

부족했던 점

처음에 풀이를 할때 패턴을 구하는데 실수를 하여서 다른 방식으로 풀었습니다. 백준에서 채점결과 피보나치를 사용하는 쪽이 더 빨랐습니다.

import java.util.Scanner;

public class Main {
    static long number[][] = new long[1001][10];

    public static long cal(int level , int num){

        long sum = 0;

            number[1][1] = 1;
            number[2][0] = 1;

        for(int i=3; i<=level; i++){
            for(int j = 0; j<num; j++){
                    if(j == 0) { number[i][j] += number[i-1][0] + number[i-1][1]; }
                    else if(j == 1){ number[i][j] += number[i-1][0];}
            }
        }

        for(int k =0; k<num; k++){
            sum += number[level][k];
        }
        return sum;
    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
            System.out.println(cal(n,2));
    }
}

11057번: 오르막 수 (acmicpc.net)

해당 문제를 풀기전 

DP - 10844(쉬운 계단 수) :: 꿈을 보는 개발자 (tistory.com)

위 문제에 대해서 이전 게시물에 포스팅하였습니다. 

오르막 수 문제도 이와 비슷한 갈피를 통해서 문제를 풀었습니다. 여기서 쉬운 계단 수와 다른 점은 쉬운 계단 수는 1과 9일 경우에만 조건을 통해서 설정 해주었지만, 이 경우에는 자리에 들어갈 숫자보다 같거나 큰 경우에만 값을 넣을 수 있습니다. 그렇기 때문에 이전 문제를 활용하여서 for을 0~9까지 검사하도록 해주고 현재 자리수의 숫자보다 크거가 값은 경우에는 값을 더해서 갱신 해주도록 하였습니다. 

package com.company;

import java.util.Scanner;

public class Main {
    static int number[][] = new int[1001][10];

    public static int cal(int level , int num){

        int sum = 0;
        for(int i =0; i<10; i++){
            number[1][i] = 1;
        }

        for(int i=2; i<=level; i++){
            for(int j = 0; j<num; j++){
               for(int n=9; n>=j; n--){
                   number[i][j] += (number[i-1][n])%10007;
               }
            }
        }

        for(int k =0; k<10; k++){
            sum += number[level][k];
        }
        return sum;
    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
            System.out.println(cal(n,10)%10007);
    }
}