22.05.17. 풀었던 문제들

1. 아이템 줍기

사각형을 바로 채워버리면 거리가 1일 때 해당 부분이 뭉개진다! 따라서 2배로 scale-up을 해야 풀 수 있었던 문제.

​

​

2. 보행자 천국

방향성을 고려해 주어야 하는 문제였다. 처음에는 회전금지 신호가 있으면 위/또는 아래에서 해당 값을 받아오는 형식으로 구현했는데 이렇게 하면 연속된 회전금지 신호일 경우 잘 나타나지 않았다. 그래서 '현 위치에서 r방향/c방향으로 갈 수 있는 경우의 수'를 만들었다. 그래서 2d vector of pii로 구현했다. dist[r][c].first는 r, c에서 r방향으로 갈 수 있는 경우의 수, .second는 c방향으로 갈 수 있는 경우의 수이다.

 

// 보행자 천국

int MOD = 20170805;

typedef pair<int, int> pii;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    vector<vector<pii>> dist(m, vector<pii>(n, {0, 0})); // dist[r][c].first : r방향, .second : c방향
    for(int i = 0; i<m; i++){
        if(city_map[i][0] == 1) break;
        dist[i][0].first = 1;
        dist[i][0].second = city_map[i][0] == 2 ? 0 : 1;
    }
    for(int i = 0; i<n; i++){
        if(city_map[0][i] == 1) break;
        dist[0][i].first = city_map[0][i] == 2 ? 0 : 1;
        dist[0][i].second = 1;
    }
    
    for(int r = 1; r<m; r++){
        for(int c = 1; c<n; c++){
            if(city_map[r][c] == 1){ // 정지신호라면 다음으로 넘어가지 못함
                dist[r][c].first = dist[r][c].second = 0;
                continue;
            }
            else if(city_map[r][c] == 2){ // 회전금지 신호라면 r방향은 r-1, c의 r방향만, c방향은 r, c-1의 c방향만 가져올 수 있음.
                dist[r][c].first = dist[r-1][c].first % MOD;
                dist[r][c].second = dist[r][c-1].second % MOD;
            }
            else{ // 방향이 상관없다면 어디든 갈 수 있음. r-1, c의 r방향 + r, c-1방향의 c방향을 가져와 더하면 됨.
                dist[r][c].first = dist[r][c].second = (dist[r-1][c].first % MOD + dist[r][c-1].second % MOD) % MOD;
            }
        }
    }
    
    return dist[m-1][n-1].first;
} // 마지막 좌표의 경우 0인 것이 보장되어 있으므로 이렇게 작성했다.

 

lv 3오니까 까다롭고, 생각해서 풀어야 할 문제가 많다...