[백준] 1309

문제 개요

주어진 문제는 2*N 크기의 우리에 사자들을 배치하는 경우의 수를 구하는 것입니다. 사자들은 가로로도, 세로로도 붙어 있을 수 없으며, 사자를 한 마리도 배치하지 않는 경우도 하나의 경우로 칩니다.

접근 방법

이 문제는 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있습니다. 접근 방법을 단계별로 설명하겠습니다.

1. 기본 아이디어:
   각 위치에 사자를 배치하는 경우와 배치하지 않는 경우를 고려하여 경우의 수를 계산합니다. 이를 위해 동적 계획법을 사용하여 이전 단계의 결과를 이용해 다음 단계를 계산합니다.

2. 점화식 유도:

   • 사자가 없는 경우: 1가지 (빈 우리)
   • 사자가 하나 있는 경우: 3가지 (왼쪽, 오른쪽, 빈칸)
   • 사자가 두 마리 있는 경우 이상부터는 이전 두 단계의 결과를 이용하여 계산할 수 있습니다. 이는 f(n+1) = 2*f(n) + f(n-1)로 표현할 수 있습니다. 여기서 f(n)은 n번째 칸까지의 경우의 수를 의미합니다.

3. 동적 계획법 배열 정의:

   • cost[i]: i번째 칸까지의 경우의 수를 저장하는 배열입니다.

코드

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

public class P1309 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] cost = new int[N+1];
        cost[0] = 1;
        cost[1] = 3;

        for(int i = 0; i < N-1; i++){
            cost[i+2] = (2*cost[i+1] + cost[i])%9901;
        }
        System.out.println(cost[N]);
    }
}

사고 과정 설명

1. 문제 이해:
   문제를 이해하는 첫 번째 단계는 사자들이 우리에 배치되는 경우의 수를 계산하는 것입니다. 사자들이 가로 또는 세로로 붙어 있을 수 없다는 조건을 고려해야 합니다.

2. 점화식 유도:
   각 단계에서의 경우의 수를 계산하기 위해 점화식을 유도했습니다. f(n+1) = 2*f(n) + f(n-1)이라는 점화식을 사용하여 다음 단계를 계산할 수 있습니다.

3. 동적 계획법 배열 정의:

   • cost[0]은 빈 우리로 1가지 경우를 가집니다.
   • cost[1]은 첫 번째 칸에 사자를 배치하는 경우로 3가지 경우를 가집니다.
   • 그 이후로는 점화식을 사용하여 각 칸의 경우의 수를 계산합니다.

4. 코드 구현:

   • BufferedReader를 사용하여 입력을 받습니다.
   • 배열 cost를 정의하고 초기값을 설정합니다.
   • for 루프를 사용하여 각 칸의 경우의 수를 계산합니다.
   • 최종 결과를 출력합니다.

결론

이 접근 방법은 동적 계획법을 사용하여 효율적으로 주어진 문제를 해결합니다. 작은 부분 문제들의 해결 결과를 결합하여 최적의 해결책을 구조적으로 찾을 수 있습니다. 동적 계획법을 활용하여 문제를 단계적으로 해결하는 방법을 배울 수 있는 좋은 예제입니다.

식 유도 과정

/*
    f(n+1) = 2*f(n) + f(n-1)
     */


    /*
    1 -> 00 01 10 : 3
    2 -> 00 01 10 00 01 10 00 01 10
         00 00 00 01 -- 01 10 10 -- : f(1) + f(1) - 1 + f(1) - 1 = 3 + 2 + 2 = 7 = 3*f(1) - 2
    3 -> 00  01  10  00  00  10  01
         00  00, 00, 10, 01, 01, 10 : 7
         00, 00, 00, 00, 00, 00, 00 :f(2) : 7
      -> 00  01  10  00  00  10  01
         00  00, 00, 10, 01, 01, 10 : 7
         01, 01, 01, 01, --, --, 01 :f(2) - 2 : 5
      -> 00  01  10  00  00  10  01
         00  00, 00, 10, 01, 01, 10 : 7
         10, 10, 10, --, 10, 10, -- :f(2) - 2 : 5

    3 -> 00  01  10  00  00  10  01
         00, 00, 00, 10, 01, 01, 10 : 7
         01  01  01  01  --  --  01 : f(2) - 2 : 5

         00
         10
         01

         00 00 00 = f(1)
         10 10 = f(1) - 1
         01 01 = f(1) - 1
         f(2) = f(1) + 2*(f(1) - 1)
         f(2) - f(1) = 2*(f(1) - 1)

         00 00 00 00 00 00 00 = f(2)
         01 01 01 01 01 = f(2) - (f(1) - 1)
         10 10 10 10 10 = f(2) - (f(1) - 1)
         f(3) = f(2) + 2*(f(2) - (f(1) - 1)) = 3*f(2) - (f(2) - f(1) = 2*f(2) + f(1)
         2*(f(2) - (f(1) - 1)) = f(3) - f(2)

         00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 = f(3)
         01 01 01 01 01 01 01 01 01 01 01 01 = f(3) - (f(2) - (f(1) - 1)) = f(3) - (f(3) - f(2)) / 2
         10 10 10 10 10 10 10 10 10 10 10 10 = f(3) - (f(2) - (f(1) - 1))
         = f(3) + f(3) + f(3) - f(3) - f(2) = 2*f(3) - f(2)
         f(4) = f(3) + 2*(f(3) - (f(2) - (f(1) - 1))) = 3*f(3) - (f(3) - f(2)) = 2*f(3) + f(2)


1 2 5 12
f(3) = f(2) + f(2) - (f(1) - 1) + f(2) - (f(1) - 1)
f(2) - (f(1) - 1) = (f(3) - f(2)) / 2
f(n+1) = 2*f(n) + f(n-1)

     */