[파이썬] [DP] 백준 23083 꿀벌 승연이

문제

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

23083번: 꿀벌 승연이

코드

import sys
sys.setrecursionlimit(3000000)
input=sys.stdin.readline
X=1e9+7

n,m=map(int, input().split())
k=int(input())
#맨 마지막 줄 아래서 위로 올라오는 예외 처리를 위해 n+2
graph=[[-1]*(m+1) for _ in range(n+2)]
#구멍은 0으로 처리
for _ in range(k):
    a,b=map(int,input().split())
    graph[a][b]=0
#n행 0열 0으로 처리
for i in range(n+2):
    graph[i][0]=0
#0행 n열 0으로 처리
for i in range(m+1):
    graph[0][i]=0
    graph[n+1][i]=0
graph[1][1]=1

def make(r,c):
    if graph[r][c]!=-1:
        return graph[r][c]
    val=make(r-1,c)+make(r,c-1)
    #홀수 열이면 r-1,c-1 케이스 추기
    if c%2==1:
        val+=make(r-1,c-1)
    #짝수 열이면 r+1,c-1 케이스 추기
    else:
        val+=make(r+1,c-1)

    graph[r][c]=int(val%X)
    return graph[r][c]

print(make(n,m))

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

public class b23083 {
    static final int MOD=1000000007;
    static long[][] arr;

    public static long recur(int n, int m){
        if (arr[n][m]!=-1) return arr[n][m];

        long res = recur(n-1,m)%MOD +recur(n,m-1)%MOD;

        //홀수 열
        if(m%2==1){
            res+= recur(n-1,m-1)%MOD;
        }
        //짝수 열
        else{
            res+= recur(n+1,m-1)%MOD;
        }

        arr[n][m]=res%MOD;
        return arr[n][m];
    }

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

        st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        int m=Integer.parseInt(st.nextToken());
        int k=Integer.parseInt(br.readLine());

        arr=new long[n+2][m+1];
        for(int i=0; i<n+2; i++){
            Arrays.fill(arr[i], -1);
        }

        for(int i=0; i<k; i++){
            st=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());
            arr[a][b]=0;
        }
        for(int i=0; i<n+2; i++){
            arr[i][0]=0;
        }
        for(int i=0; i<m+1; i++){
            arr[0][i]=0;
            arr[n+1][i]=0;
        }

        arr[1][1]=1;
        System.out.println(recur(n,m));
    }
}

시간 복잡도

메모리제이션하면 부분문제에서 또 파생되는 부분문제의 가지를 모두 생략할 수 있다. 문제의 개수 x 문제 1개를 푸는 시간

 

어려웠던 부분

맨 아래에서 위로 올라오는 경우 예외처리 하는 법이 까다로웠고, 열이 홀수이냐 짝수이냐에 따라 케이스를 나누는 것이 어려웠다.