꿈을 보는 개발자

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

10844번: 쉬운 계단 수 (acmicpc.net)

쉬운 계단 수 문제였지만 마냥 쉽지만은 않았습니다. 우선 2차원 배열을 활용하여서 자리수가 낮은 수부터 결과값을 갱신해 나가는 형태를 보였습니다. 2차원 배열을 활용한 이유는 자리수와 자리수에 나오는 숫자에 따라서 결과가 나누어 지기때문에 자리수와 자리수에 나오는 숫자에 따른 결과를 구분해주기 위해서 2차원 배열을 사용했습니다. 

이때, 문제가 되는 부분은 숫자 0과 9입니다. 숫자가 0일 경우 다음에 나올 수는 계단수 조건을 충족하기 위해서는 1만 나오고 9일 경우에는 8만 나올수 있습니다. 따라서 값을 갱신 할 때, 이 두개의 숫자가 나올 경우의 조건을 따로 설정해주어야할 필요가 있었습니다. 

Bottom - up 방식을 통해서 아래의 코드를 작성하였습니다. 

package com.company;

import java.util.Scanner;




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

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

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

        for(int i=2; i<=level; i++){
            for(int j = 0; j<num; j++){
                if(j == 0){
                    number[i][j] = (number[i-1][1])%1000000000;
                }
                else if(j == 9){
                    number[i][j] = (number[i-1][8])%1000000000;
                }
                else{
                    number[i][j] = (number[i-1][j+1] + number[i-1][j-1])%1000000000;
                }
            }
        }

        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)%1000000000);
    }
}

이때, 값을 갱신해줄 때마다 문제의 조건처럼 1000000000의 나머지값을 갱신 해주었습니다. 

부족했던 점

이전과 같이 Top-down 방식으로 풀어보고 싶었으나 갈피를 잡지 못하였습니다. 계속 생각해도 풀리지 않아서 다른 풀이를 참고하여서 2차원 배열을 사용해야 함을 알았고 이를 통해서 문제를 풀어나갔습니다. 위와 비슷한 경우의 문제도 이를 참고하여서 풀 수 있어야 합니다. 

9095번 제출 (acmicpc.net)

적절한 점화식을 찾는것이 중요합니다. 1,2,3만을 통해서 합을 나타내는 수를 출력해야하므로 4에 대한 합을 찾는다 가정하였을때 

4일 경우 경우의 수는 

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

즉, 7 = 4 + 2 + 1 -> f(4) = f(3) + f(2) + f(1)다음과 같이 바꿀 수 있습니다. 

5일 경우까지 해본다면, 

• 1+1+1+1+1
• 2+1+1+1
• 1+2+1+1
• 1+1+2+1
• 1+1+1+2
• 2+2+1
• 2+1+2
• 1+2+2
• 3+1+1
• 1+3+1
• 1+1+3
• 3+2
• 2+3

총 13가지가 나오고 

13 = 7 + 4 +2 -> f(5) = f(4) + f(3) + f(2)라는 결과가 나옵니다.

점화식으로는  f(n) = f(n-1) + f(n-2) + f(n-1)으로 나타 낼 수 있습니다. 이를 재귀방식으로 코드를 짠다면,

package com.company;

import java.util.Scanner;




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

    public static int cal(int n){

        result[0] = 1;
        result[1] = 1;
        result[2] = 2;
        result[3] = 4;

        if(result[n] != 0 ){
            return  result[n];
        }
        else {
            result[n] = (cal(n - 1) + cal(n - 2) + cal(n-3)) % 10007;
        }

        return result[n];
    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i = 0; i<n; i++){
            int num = sc.nextInt();
            System.out.println(cal(num));
        }


    }
}

다음과 같은 코드를 만들 수 있습니다. 

본 문제는 2xn 타일링 문제입니다. 이 문제의 핵심은 적절한 점화식을 찾아내는 것입니다.

11726번: 2×n 타일링 (acmicpc.net)

우선 그림으로 타일들을 나타낸다면,

다음과 같은 패턴을 볼 수 있습니다. 이 경우에 점화식을 찾아내게 된다면 

F(n) = F(n-1) +F (n-2) 의 점화식을 구할 수 있고 이를 이번에는 재귀함수를 통해서 TOP-DOWN 방식을 통해 풀어내게 된다면, 다음과 같은 코드가 나오게 됩니다.

package com.company;

import java.util.Scanner;

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

    public static int domino(int n){

        result[0] = 1;
        result[1] = 1;
        result[2] = 2;

        if(result[n] != 0){
            return result[n];
        }
        else{
            result[n] = (domino(n-1) + domino(n-2))%10007;
        }

        return result[n];
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(domino(n)%10007);

    }
}

이와 연계 하여서 11727문제도 점화식 변경하는 식으로 풀어냈습니다. 

11727번: 2×n 타일링 2 (acmicpc.net)

부족했던 점

처음 시도를 하였을때는 아래의 코드와 같이

package com.company;

import java.util.Scanner;




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

    public static int domino(int n){

        result[0] = 1;
        result[1] = 1;
        result[2] = 2;
        if(n == 0) return result[0];
        if(n == 1) return result[1];
        if(n == 2) return result[2];


        result[n] = (domino(n-1) + domino(n-2))%10007;


        return result[n];
    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(domino(n)%10007);

    }
}

이미 결과값을 구한 배열일때도 연산을 다시 하도록 해주서어서 시간이 더 오래걸려 시간제한조건을 충족하지 못했습니다. 이를 해결하기 위해서 점화식 결과값을 리턴하기전 다음과 같은 조건을 삽입해주 이미 배열속에 값이 있는 경우에는 바로 값을 리턴해주도록 하였습니다. 

        if(result[n] != 0){
            return result[n];
        }

1463번: 1로 만들기 (acmicpc.net)

처음으로 풀어볼 DP문제입니다. 

우선은 DP문제이기 때문에 인접한 값들의 영향을 받는 구조가 나옵니다.

따라서 해당 문제에 해당하는 알맞은 점화식을 구하는 것을 가장 최우선으로 생각했습니다.

정수 X에 대하여 사용할 수 있는 연산은 

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

최소값을 구하기 위해서 가장 먼저 생각했던것은 숫자를 3으로 최대한 나누고 2로 최대한 나눈후 1로 빼는 방식을 사용했습니다. 다만, 10일 경우에는 최우선으로 10에 1을 빼고 계산을 하는 것이 2로 먼저나누는 경우보다 더 적은 연산값을 가집니다. 

그렇기 때문에 이같은 방식 보다 2부터 시작하여서 2나 3으로 나누어지기전 1을 빼는 연산을 하는 경우를 미리 결과값을 넣어줄 배열에 넣어놓은후 min 함수를 통해서 2혹은 3으로 나누는 경우와 -1을 하는 경우의 최소값을 구해서 연산값이 더 적은 경우를 선택하는 방식을 사용하였습니다. 

package com.company;

import java.util.Scanner;
import java.lang.Math;



public class Main {

    public static int one(int n){
        int num[] = new int[n+1];
        num[0] = 0;
        num[1] = 0;

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

            num[i] = num[i-1] + 1; 
            if(i%2 == 0){ num[i] = Math.min(num[i], num[i/2]+1); }
            if(i%3 == 0){ num[i] = Math.min(num[i], num[i/3]+1); }

        }
        return num[n];
    }



    public static void main(String[] args) {

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

    }
}