안녕하세요. 오랜만에 카카오 코드 페스티벌 풀이를 쓰네요.문제가 어렵다 보니 쉽게 손이 안 갑니다. ㅎㅎ 4번 문제는 https://www.welcomekakao.com/learn/challenges/630 에서 확인하실 수가 있습니다. 동적계획법으로 푸는 문제인데요. 저는 도중에 몰라서 간단하게 설명된카카오의 풀이를 참고했습니다. 풀이를 보면 동적계획법(DP)을 아시는 분이면 푸실 수가 있는데요.주의하실 점은 나머지 연산(모듈로 연산)입니다. 처음에 저는 마지막 리턴 값에 만 나머지 연산을 적용해서계속 정답 처리를 못 받고 있었는데, 값을 계산할 때 매번 해줘야 한다고 다른 분들께서 알려주셨어요.그리고 저는 dp의 크기를 최대 입력값 500보다 하나 크게 잡았습니다.i, j 위치에서 값을 계산할 때 i-1, j-1의 값을 불러오기 때문에 0인 경우에 인덱스 범위를 벗어나서if문을 넣어 계속 체크를 해주는 것보다는 0행과 0열에 0으로 된 값을 넣어서 해결했습니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <vector> 
#include <cstring>

using namespace std;

int MOD = 20170805;  // 나머지 연산에 쓰이는 수

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int r[501][501]; //i,j위치에서 오른쪽으로 갈 수 있는 경우의 수 
int b[501][501]; //i,j 아래쪽으로 갈 수 있는 경우의 수 
int solution(int m, int n, vector<vector<int>> city_map) {
    memset(r, 0, sizeof r);
    memset(b, 0, sizeof b);
    MOD = 20170805;
    r[1][1] = b[1][1] = 1; //첫 위치에서는 아래쪽이나 오른쪽으로 갈수 있는 한 가지의 경우에서 출발
    
    for(int i=1; i<=m;i++){   
        for(int j=1;j<=n;j++){
            if(city_map[i-1][j-1]==0){
                r[i][j] = (r[i][j] + r[i][j-1] + b[i-1][j])%MOD; //0인 경우 왼쪽이나 위쪽에서 오는 경우를 더하면 됨
                b[i][j] = (b[i][j] + r[i][j-1] + b[i-1][j])%MOD; //0인 경우 왼쪽이나 위쪽에서 오는 경우를 더하면 됨
            }
            else if(city_map[i-1][j-1]==1){
                r[i][j] = 0; //1인 경우 막혀서 갈 수가 없음
                b[i][j] = 0; //1인 경우 막혀서 갈 수가 없음 
            }
            else{
                r[i][j] = r[i][j-1]; //2인 경우 왼쪽에서 오는 차량만 지나갈 수 있음
                b[i][j] = b[i-1][j]; //2인 경우 왼쪽에서 오는 차량만 지나갈 수 있음                                
            }
        }
    }
    
    return (r[m][n-1]+b[m-1][n])%MOD; //목적지까지 갈 수 있는 경우의 수는 왼쪽에서 오는 경우와 위쪽에서 오는 경우를 더한 것임
}