백준 20165 인내의 도미노 장인 호석 혼내주기

 

제 1회 류호석배 알고리즘 코딩 테스트 문제.

 

구현 문제. 도미노가 쓰러질 때 연달아 쓰러지는 경우 앞으로 쓰러질 여지?가 가장 많은 도미노의 개수를 계속 업데이트 하면서 쓰러지면 된다. 

 

통과 후 질문을 확인해보니 내 코드가 통과하지 않는 반례가 있었다. 공격수가 처음 공격하는 도미노가 넘어진 상태면 아무일도 일어나야 하지 않는데, 이 예외에 대한 처리가 안되있어서 수정해서 제출했다.

 

나는 아직 문제를 풀 때 반례를 떠올리는 능력이 부족한데, 이렇게 반례를 찾아내는 사람들을 보면 참 부럽다. 노력으로 극복할 수 있을까?

 

#include <iostream>
using namespace std;

int map[101][101];
bool res[101][101]; //  0 S 1 F


int main(){
    int n, m, r;
    cin >> n >> m >> r;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> map[i][j];
        
    int x, y, tot = 0;
    char d;
    
    while(r--){
        cin >> x >> y >> d;

        int cnt = map[x][y], idx = 0, dx = 0, dy = 0;

        if(res[x][y]) cnt = 0;
        if(d == 'E') dy = 1;
        else if(d == 'W') dy = -1;
        else if(d == 'S') dx = 1;
        else if(d == 'N') dx = -1;
        
        while(cnt){
            if(x < 1 || x > n || y < 1 || y > m) break;
            
            if(res[x][y] == 0){
                res[x][y] = true;
                tot++;
                if(cnt < map[x][y]) cnt = map[x][y];
            }
            x += dx; y += dy;
            cnt--;
        }
        
        cin >> x >> y;
        res[x][y] = false;

    }
    cout << tot << "\n";
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(res[i][j] == 0) cout << "S ";
            else cout << "F ";
        }
        cout << endl;
    }

}