글 읽기 - 시간초과 질문

creampuffshu 3년 전 0

처음에 메모제이션 없이 해서 시간초과 나길래 메모제이션 해봤긴 했는데 아직도 50%에서 시간초과가 나네요..

잘못된 부분 알려주시면 감사하겠습니다.

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;

int n,m,k;
string goal;
char a[100][100];
int ans=0;
int dist[100][100][80];
int dx[] = {1,0,0,-1};
int dy[] = {0,1,-1,0};
int d(int x, int y, int index){
    for(int i=0;i<4;i++){
        for(int j=1;j<=k;j++){
            int nx = x+dx[i]*j;
            int ny = y+dy[i]*j;
            if(nx>=0&&nx<n&&ny>=0&&ny<m){
                if(a[nx][ny]==goal[index]){
                    if(dist[nx][ny][index+1]!=0){
                        dist[x][y][index] += dist[nx][ny][index+1];
                    }
                    else if(index==goal.size()-1){ 
                        dist[x][y][index]++;
                    }
                    else dist[x][y][index] += d(nx,ny,index+1);
                    
                }
            }
        }
    }
    return dist[x][y][index];
}
int main(void){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n>>m>>k;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        for(int j=0;j<m;j++){
            a[i][j]=s[j];
        }
    }
    cin>>goal;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]==goal[0]){
                ans += d(i,j,1);
            }
        }
    }
    cout<<ans;
    return 0;
}

xofyd99 3년 전 2

dist 배열에 따로 초기화를 안 해줘서 값이 0일 거 같은데요, 그러면 0이 두 가지 의미를 지닐 것 같아요.

1. 아직 방문하지 않은 곳

2. 문자열을 하나도 만들 수 없는 곳

그래서 시간초과 날 것 같네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 질문

creampuffshu 3년 전 0

xofyd99 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말