StepByStep

https://www.acmicpc.net/problem/1256

문제

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다.

규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다.

N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 규완이의 사전에서 K번째 문자열을 출력한다. 만약 규완이의 사전에 수록되어 있는 문자열의 개수가 K보다 작으면 -1을 출력한다.

접근 방법

1. N, M, K의 범위를 봤을 때 100,100, 10억이고, N,M개의 같은 것이 있는 수열임을 볼 때 DP문제임을 알 수 있다.

2. 문자 A,Z가 N개 M개로 만들 수 있는 개수는 A,Z 가 N-1,M개와 N,M-1개로 만들 수 있는 개수의 합과 같다.

3. 이를 통해 K와 N+M개로 만들 수 있는 수를 비교 하면서 앞에서 부터 A인지 Z인지 하나씩 만들면서 정답을 도출한다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static double[][] dp;
    static BufferedWriter answer = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int N,M,K;
	    N = Integer.parseInt(st.nextToken());
	    M = Integer.parseInt(st.nextToken());
	    K = Integer.parseInt(st.nextToken());
        dp = new double[N + 1][M + 1];


        if(K>numWord(N,M)) {
            System.out.println("-1");
        }else {
            getWord(N,M,K-1);
        }
        answer.write("\n");
    answer.close();
    }
    static double numWord(int A, int Z){
        if(A==0||Z==0)
            return 1;
        if(dp[A][Z]!=0)
            return dp[A][Z];
        return dp[A][Z]= Double.min(numWord(A-1,Z)+numWord(A,Z-1), 1000000001);
    }

    static void getWord(int A, int Z, double before) throws IOException {
        if(A==0) {
            for (int i = 0; i < Z; i++)
                answer.write("z");
            return;
        }
        if(Z==0){
            for (int i = 0; i < A; i++) 
                answer.write("a");
            return;
            
        }
        double tmp = numWord(A-1, Z);

        if(before < tmp){
            answer.write("a");
            getWord(A-1,Z,before);
        }else {
            answer.write("z");
            getWord(A,Z-1,before-tmp);
        }
    }
}

https://www.acmicpc.net/problem/2560

문제

한 생물학자가 새로 발견된 짚신벌레 종의 생태에 대해 연구하고 있다. 매우 번식력이 강하다고 알려진 이 종은 아래와 같은 특징을 가지고 있다.

무성 생식을 한다.

태어난 이후 a일째 되는 날 성체가 된다.

성체가 된 날부터 매일 한 마리씩 새로운 개체를 만들어낸다: 성체가 되자마자 첫 개체를 만들어내고, 그 이후로 하루가 지날 때마다 새로운 개체를 하나씩 만들어낸다. 새로운 개체 역시 태어난 이후로 a일째 되는 날부터 성체가 되어 새로운 개체를 만든다.

태어난 이후로 b일째 되는 순간부터는 새로운 개체를 더 이상 만들지 않는다. 태어난 지 a일째 날부터 b일째 되는 날의 전날까지 새로운 개체를 만들어내므로 일생동안 총 b-a 마리의 개체를 만들어낸다.

태어난 이후로 d일째 되는 순간 죽는다.

아래는 a=2, b=4, d=6일 때 수조에 새로 태어난 짚신벌레 한 마리를 넣고 매일 관찰한 결과를 기록한 것이다. 괄호 안의 숫자들은 수조 안의 짚신벌레들이 각각 태어난 이후 며칠이 되었는지를 나타내는 정수이다.

태어난 날: (0) - 새로운 개체를 집어넣음

1일째 되는 날: (1) - 짚신벌레가 자람

2일째 되는 날: (2, 0) - 짚신벌레가 태어난 지 2일째가 되므로 성체가 되고 새 개체를 만들어 냄

3일째 되는 날: (3, 1, 0) - 2일째 성체가 된 짚신벌레가 오늘도 새 개체를 하나 만들어 냄

4일 째 되는 날: (4, 2, 1, 0) - 2일째 되는 날 만들어진 짚신벌레가 새로운 개체를 만들어 냄 (처음에 넣은 짚신벌레는 새 개체를 만들어내지 못함)

5일 째 되는 날: (5, 3, 2, 1, 0, 0)

6일 째 되는 날: (4, 3, 2, 1, 1, 0, 0) - 처음에 넣은 개체는 죽는다.

6일 째 되는 날 수조안에 살아있는 짚신벌레는 총 7마리가 된다.

짚신벌레의 번식 정보 a, b, d에 대하여, 새로 태어난 짚신벌레 한 마리를 수조 안에 넣은 이후 N일째 되는 날 살아있는 짚신벌레 수를 1000으로 나눈 나머지를 출력하는 프로그램을 작성하시오.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력

첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d≤10,000이고, 1≤N≤1,000,000이다.

출력

첫째 줄에, 수조에 짚신벌레 한 마리를 넣은 지 N일째 되는 날 수조에 살아 있는 짚신벌레의 수를 1000으로 나눈 나머지를 출력한다.

풀이

a일 부터 무성생식이 가능하므로 a까지는 1마리로 유지된다. 이후로 b일까지 생식을 진행하므로 계속 증가한다. 이때 b일 전까지의 벌레의 마리수는 전날 + 오늘 새로 태어난 벌레의 수이다. 그래서  dp[i] = dp[i-1] + dp[i-a] 이다. 

오늘 태어난 벌레의 수는 오늘 부터 a일 전에 있던 벌레의 수이다.

하지만 b일 이후에는 더이상 생식을 하지 않기에 b일 이후의 벌레는 dp[i] = dp[i - 1] + dp[i - a] - dp[i - b] 이다. 이렇듯 더이상 생식을 하지 않은 벌레 수를 빼주면서 더해간다.

그리고 d일 이후에는 죽은 벌레의 수를 빼주면 된다.

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

public class Main {

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

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        int death = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[] dp = new int[N+1];
        dp[0] = 1;

        for (int i = 1; i <= N; i++) {
            if (i<start) // 시작날 전까지 유지됨.
                dp[i] = dp[i-1]%1000;
            else if(i<end) // 단순하게 증가함! 전날 + 새로 태어남
                dp[i] = (dp[i-1] + dp[i-start])%1000;
            else
                dp[i] = (dp[i-1]+dp[i-start]-dp[i-end]+1000)%1000;
        }

        if(N-death>=0)
            System.out.println((dp[N]-dp[N-death]+1000)%1000);
            
        else System.out.println(dp[N]%1000);

    }
}

문제

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

출력

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

풀이

이 문제는 DP문제로 시간이 1초임을 유의해서 풀어야 한다.

단순한 아이디어로 풀수 있는 문제이다.

왼쪽 끝과 오른쪽 끝은 내려갈 수 있는 곳이 2곳으로 한정되어 있고, 중간은 세 곳 모두 갈 수 있으므로 연산을 최대와 최소만 찾아서 구해주면 답은 나온다.

괜히 이 방법이 아닐까봐 다른 방법을 생각해보다가 시간이 오래 걸렸다.

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

public class Main {
    static int N;
    public static void main(String[] args) throws IOException {
    
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int[] input = new int[3];
        int[][] dp = new int[N][6];
        
        for (int i = 0; i < 3; i++)
            input[i] = Integer.parseInt(st.nextToken());
       
       for (int i = 0; i < 3; i++) 
            dp[0][3 + i] = dp[0][i] = input[i];
        

        for (int k = 1; k < N; k++) {
        
            st = new StringTokenizer(bf.readLine());
            
            for (int j = 0; j < 3; j++)
                input[j] = Integer.parseInt(st.nextToken());
                
            int i = k-1;
            
            dp[k][0] = Integer.min(dp[i][0], dp[i][1]) + input[0];
            dp[k][1] = Integer.min(dp[i][0], Integer.min(dp[i][1], dp[i][2])) + input[1];
            dp[k][2] = Integer.min(dp[i][1], dp[i][2]) + input[2];

            dp[k][3] = Integer.max(dp[i][3], dp[i][4]) + input[0];
            dp[k][4] = Integer.max(dp[i][3], Integer.max(dp[i][4], dp[i][5])) + input[1];
            dp[k][5] = Integer.max(dp[i][4], dp[i][5]) + input[2];
        }

        Arrays.sort(dp[N-1]);
        System.out.printf("%d %d",dp[N-1][5],dp[N-1][0]);

    }
}