강의로 돌아가기
정혜미

효율성 질문드립니다.

#include <string>
#include <vector>

using namespace std;
vector<vector<int>>mem; // 여태 계산한 경로 수 저장
vector<vector<int>>pmap; // 웅덩이 위치 저장

void makepmap(vector<vector<int>>puddles){ //웅덩이 위치 저장하는 맵 만들기
    for(int i = 0 ; i < puddles.size(); i++){
        pmap[puddles[i][0]-1][puddles[i][1]-1] = 1;
    }
    return;
}

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    mem.resize(m);
    pmap.resize(m);
    for(int i = 0 ; i < m ; i++){
        mem[i].resize(n);
        pmap[i].resize(n);
    }
    makepmap(puddles);
    mem[0][0] = 1;
    for(int i = 0 ; i < m ; i++){
        for(int j = 0 ; j < n ; j++){
            if(pmap[i][j] == 1){ //웅덩이 만났을때
                mem[i][j] = 0;
            }
            else{

                if(i == 0 && j != 0){ //가장자리
                    mem[i][j] = mem[i][j-1];
                }
                else if(i != 0 && j == 0){ //가장자리
                    mem [i][j] = mem[i-1][j];
                }
                else if(i != 0 && j != 0){ //가장자리가 아닌 좌표
                    mem[i][j] = (mem[i-1][j] + mem[i][j-1])%10000000007;
                }
            }
        }
    }
    answer = mem[m-1][n-1];
    return answer;
}

메모이제이션으로 2차원 배열 써서 풀었는데 효율성은 꽝이네요...
혹시 다른 방법 있을까요?

0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.