개발 블로그

문제 링크 : https://www.acmicpc.net/problem/10164

접근 방법

처음에는 조합으로 풀었다가 32점이 나와서 dp로 문제를 해결했다.

처음 접근 방법은 K가 0이 아니면

K의 좌표를 구한 다음 -> 그 좌표까지 가려면 우측 방향으로 몇번 가야하는지와 아래 방향으로 몇 번 가야하는지를 조합을 사용해서 계산햇다. 

예제를 예시로 들면 아래에서 K까지 가려면 처음 [0][0]에서 우측으로 두 번, 아래 방향으로 한 번 가면 되는 것이다.

총 세번 이동을 해야하는데 그 중에 아래 화살표들을 순서 상관 없이 나열하는 조합의 경우의 수를 구하면 된다. 

➡️➡️⬇️

➡️⬇️➡️

⬇️➡️➡️

import java.util.Scanner;

public class Main {

    static int combi(int n, int r){
        if(n==r || r==0) return 1;
        return combi(n-1, r-1) + combi(n-1,r);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int K = sc.nextInt();
        int ans = 0;

        if(K!=0){
            int kRow = K/M;
            int kCol = K%M -1;

            int first = combi(kRow+kCol, kCol);
            int second = combi(M-kCol-1 + N-kRow-1, N-kRow-1);
            ans = first*second;
        }
        else{
            ans = combi(N+M-2, N-1);
        }
        System.out.println(ans);

    }
}

그러나 이 방법으로는 32점밖에 안 나와서 N,M이 커지면 서브테스크 3번부터 막히는 것 같아 dp로 다시 풀었다.

dp로 풀때 주의할 점은 K의 위치를 잘 구해야 한다는 것이다.

예제로 주어진 문제로만 푸는 것이 아니라

반레로 K가 M으로 딱 나눠서 떨어지는 경우 즉 입력 값이 (2, 2, 2) 인 케이스도 생각하면 서브 테스크 3,4번도 모두 맞출 수 있다

import java.util.Scanner;

public class BJOJ_10164_격자상의경로 {

    static int combi(int n, int r){
        if(n==r || r==0) return 1;
        return combi(n-1, r-1) + combi(n-1,r);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int K = sc.nextInt();
        int ans = 0;
        int[][] dp = new int[N][M];
        dp[0][0] = 0;

        if(K!=0){
            int kRow = K/M;
            int kCol = K%M;
            if(K%M == 0) {		//K가 오른쪽 끝에 붙어있는 경우 고려
                kRow -= 1;
                kCol = M-1;
            }else kCol-=1;


            for(int i = 1; i<=kRow; i++) {
                dp[i][0] = 1;
            }
            for(int i = 1; i<=kCol; i++){
                dp[0][i] = 1;
            }
            for(int i = 1; i<=kRow; i++){
                for(int j = 1; j<=kCol; j++){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
            for(int i = kRow+1; i<N; i++) dp[i][kCol] = dp[kRow][kCol];
            for(int j = kCol+1; j<M; j++) dp[kRow][j] = dp[kRow][kCol];
            for(int i = kRow+1; i<N; i++){
                for(int j = kCol+1; j<M; j++){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }

        }
        else{
            for(int i = 1; i<N; i++) {
                dp[i][0] = 1;
            }
            for(int i = 1; i<M; i++){
                dp[0][i] = 1;
            }
            for(int i = 1; i<N; i++){
                for(int j = 1; j<M; j++){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        System.out.println(dp[N-1][M-1]);


    }
}

문제 링크 : https://www.acmicpc.net/problem/2240

7 2
2
1
1
2
2
1
1

6

접근 방법

처음에는 자두의 위치를 1) 그대로 있는 경우와 2) 옆 나무로 움직이는 경우 두 가지 케이스로 분류하려고 했으나, 자두의 위치 외에도 고려해야할 변수가 두개가 더 있었다. ( 현재 몇초인지(t)와 t초에 몇번째 자두나무에서 자두가 떨어지는지) 

즉 총 세개의 변수를 고려해야함을 알았는데

추가로 매 t초마다 하는 선택이 최선의 선택이 아니며, 그렇다고 모든 경우의 수를 다 조사해 볼 수는 없기 때문에 dp로 풀기로 했다. 

dp 배열 및 각 인덱스 의미는 다음과 같다. 

dp[t][w][1] : 현재 t초이며(t초 지남), t초까지 w만큼 이동했고, 그때의 자두의 현재 위치는 1일 때 -> 먹을 수 있는 자두의 최대 갯수

dp[t][w][2] : 현재 t초이며(t초 지남), t초까지 w만큼 이동했고, 그때의 자두의 현재 위치는 2일 때 -> 먹을 수 있는 자두의 최대 갯수

이제 및 [몇번째 자두나무에서 자두가 떨어지는지] 및 [자두의 이동 여부] 케이스를 분류해서 생각해보자.

각각 2가지 경우의 수가 있다. 

-> 1번째 자두나무에서 자두가 떨어지거나 or 2번째 자두나무에서 자두가 떨어지거나

-> 그대로 있거나 Or 옆 나무로 이동하거나

Case1. 1번째 자두나무에서 자두가 떨어질 때

경우 1) 현재 자두가 1번에 있을 때 : 자두 먹을 수 있음

//자두가 t초째에 1번 자두나무 아래에 있을 때 (자두 먹은 케이스)
dp[t][w][1] = Math.max(dp[t-1][w][1], dp[t-1][w-1][2])+ 1;

=> 해석 : 1초 전에, 안 움직이고(w그대로), 1번에 있을 때 (안 움직여서 1번 그대로)

          vs 1초 전에, 움직이고 (w-1), 2번에 있을 때(2번에 있었으니까 1번으로 옮긴것)

중에 최대값을 구하고, 거기에 1을 더한다. 1을 더한 이유는

1번째 자두나무에서 자두가 떨어지는 Case1. 일 때

현재 자두의 위치가 1번 나무 아래에 있는 경우1) 이기 때문이다. 

경우 2) 현재 자두가 2번에 있을 때 : 자두 못 먹음 

//자두가 t초째에 2번 자두나무 아래에 있을 때
dp[t][w][2] = Math.max(dp[t-1][w-1][1], dp[t-1][w][2]);

=> 해석 : 1초 전에, 움직이고 (w-1), 1번에 있을 때 (1번에 있었으니까 2번으로 옮긴 것)) 

          vs 1초 전에, 안 움직이고(w그대로), 2번에 있을 때(안 움직여서 2번 그대로)

중에 최대값을 구하고, 이번엔 1을 안 더한다. 안 더한 이유는

1번째 자두나무에서 자두가 떨어지는 Case1. 일 때

현재 자두의 위치가 2번 나무 아래에 있는 경우2) 이기 때문이다. 

이런 방식으로 매 시간에 따라(t가 1부터 T일때까지)

w가 1일때부터 W일때까지 dp를 채워나간다. 

그리고 마지막에 모든 w에 대해서 dp[T][w][1], dp[T][w][2] 값 들 중에 최대값을 구한다. 

import java.util.*;

public class BOJ_2240_자두나무 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int W = sc.nextInt();
        int treeArr[] = new int[1001];
        int dp[][][] = new int[T+1][W+1][3];
        treeArr[0] = 1; //맨 처음 1번 나무에서 시작
        for(int i = 1; i<=T; i++){
            treeArr[i] = sc.nextInt();
        }

        //초기 값 셋팅
        if(treeArr[1] == 1){    //1초일 때, 첫번째 자두가 1번 나무에서 떨어질 경우(초기에 자두는 1번 나무 아래 있음)
            dp[1][0][1] = 1;    //1초일 때, 0번 움직여서, 현재 위치 그대로(1)   -> 자두 1개 먹음 (안움직이고 먹음)
            dp[1][1][2] = 0;    //1초일 때, 1번 움직여서, 현재 위치 바뀌고(2로) => 자두 0개 먹음 (움직이고 못먹음)
        }
        else{                   //1초일 때, 첫번째 자두가 2번 나무에서 떨어질 경우
            dp[1][0][1] = 0;    //1초일 때, 0번 움직이고, 현재 위치 그대로(1) -> 자두 0개 먹음 (안움직이고 못먹음)
            dp[1][1][2] = 1;    //1초일 때, 1번 움직이고, 현재 위치 바뀌고(2로) -> 자두 1개 먹음 (움직이고 먹음)

        }


        for(int t = 2; t<=T; t++){

            if(treeArr[t] == 1){    //1번 자두나무에서 자두가 떨어질 때
                //w = 0일 때 (안 움직였을 때) 현재 위치에 따른 초기 값 셋팅
                dp[t][0][1] = dp[t-1][0][1] + 1;    //현재 위치 1이면 = 0번 움직이고, 현재 위치 그대로 (안 움직이고 먹음)
                dp[t][0][2] = dp[t-1][0][2];        //현재 위치 2이면 = 0번 움직이고, 현재 위치 그대로 (안 움직이고 못 먹음)

                for(int w = 1; w<=W; w++){
                    //자두가 t초째에 1번 자두나무 아래에 있을 때 (자두 먹은 케이스)
                    dp[t][w][1] = Math.max(dp[t-1][w][1], dp[t-1][w-1][2])+ 1;
                    //자두가 t초째에 2번 자두나무 아래에 있을 때
                    dp[t][w][2] = Math.max(dp[t-1][w-1][1], dp[t-1][w][2]);
                }
            }

            else{                   //2번 자두나무에서 자두가 떨어질 때
                //w = 0일 때 (안 움직였을 때) 현재 위치에 따른 초기 값 셋팅
                dp[t][0][1] = dp[t-1][0][1];        //현재 위치 1이면 = 0번 움직이고, 현재 위치 그대로 (안 움직이고  못 먹음)
                dp[t][0][2] = dp[t-1][0][2] + 1;    //현재 위치 2이면 = 0번 움직이고, 현재 위치 그대로 (안 움직이고 먹음)



                for(int w = 1; w<=W; w++){
                    //자두가 t초째에 1번 자두나무 아래에 있을 때
                    dp[t][w][1] = Math.max(dp[t-1][w][1], dp[t-1][w-1][2]);
                    //자두가 t초째에 2번 자두나무 아래에 있을 때 (자두 먹은 케이스)
                    dp[t][w][2] = Math.max(dp[t-1][w-1][1], dp[t-1][w][2]) + 1;
                }
            }


        }

        int ans = 0;    //최대 값을 구해야 함
        for(int w = 0; w<=W; w++){
            ans = Math.max(ans, Math.max(dp[T][w][1], dp[T][w][2]));
        }
        System.out.println(ans);
    }
}

문제 링크 : www.acmicpc.net/submit/11727/26381160

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

접근 방법

가로의 길이가 1부터 n이 될 때까지 타일을 붙여나가며, 이때 두가지 케이스로 나눠서 경우의 수를 카운트했다.

붙여야하는 타일의 가로 길이가 1인 것과 2인 것을 나눴다.

Case 1) 가로 길이가 1인 타일을 붙여야 하는 경우

이 경우는 타일의 길이가 n-1가 되도록 붙이는 경우의 수와 같다. 길이가 n인 타일을 만드려면 n-1 타일에 2x1 타일을 추가하기만 하면 되기 때문이다.

Case 2) 가로 길이가 2인 타일을 붙여야 하는 경우

이 경우엔 두가지 경우로 또 나눠서 생각해야한다. 

2-1) 1x2 타일을 붙이는 경우(세로로 두개)

이 경우는 타일의 길이가 n-2가 되도록 붙이는 경우의 수와 같다. 길이가 n인 타일을 만드려면 n-2 타일에 1x2 타일 두개를 세로로 추가하기만 하면 되기 때문이다.

2-2) 2x2 타일을 붙이는 경우 

이 경우도 2-1과 같다. 2x2 타일을 추가만 하면 된다.

Case 1, 2를 조합해서 생각하면, 길이 n인 타일을 붙이는 경우의 수는,

길이 n-1인 타일을 붙이는 경우의 수 + 2*(길이 n-2인 타일을 붙이는 경우의 수) 로 나타낼 수 있다.

즉, dp[n] = dp[n-1] + 2*dp[n-2]인 것이다.

#include <iostream>
#include <vector>

using namespace std;

int dp[1001] = {0};

int main(){
    
    int n;
    cin >> n;
    
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 3;
    
    for(int i = 3; i<=n; i++){
        dp[i] = (2*dp[i-2] + dp[i-1]) % 10007;
    }
    cout << dp[n];
    
    return 0;
}

이때 주의할 점은 for문 안에서 dp[n] = dp[n-1] + 2*dp[n-2] 로 계산을 쭉 하고

마지막에 출력할 때 dp[n]%10007 을 하면 안된다는 것이다. 위의 코드와 같이 for문 안에서 나머지 계산을 해줘야한다.

문제 요구조건 자체가 mod 연산을 한 결과를 출력하라고 했으니, 처음에 dp[]에 값을 저장할 때 mod연산의 결과를 저장해야한다.