23.08.16. 풀었던 문제들 복기

9646. 다이어그램과 태블로, 2시간

 딱 보면 backtracking + purning으로 푸는 문제.

 일단 아래로 내릴 수 있으면 내리고, 너무 많이 내려간 경우 다음 col로 넘어가는 형식으로 구현했다.

 그러면 backtracking의 종료조건은 마지막 col을 탐색하고, 다음 칸을 탐색할 때 answer++를 해 주면 된다.

 다음으로, backtracking 과정은

• 위/왼쪽에 있는 값을 보고 조건을 맞춘다.
• 여기서 하나 purning을 하는데, 아래 칸으로 내릴 수 있으면 바로 내리고, 그렇지 않으면 바로 다음 col을 탐색한다.
  • 만약 이 과정을 recurse()에서 if문으로 걸면 call stack이 1번씩 더 쌓인다. worst case 모든 경우에 하나씩 더 쌓이게 되므로 이 과정을 여기로 뺀다.
• 이것만으로 충분했다.

int k, N, num_col[8], board[8][8], answer;
// num_col[i] : i번째 row의 col 개수

// recurse(row, col) - row, col에서 backtrack
void recurse(int row, int col){
    // top-down recurse 종료조건
    if(row == 0 && num_col[row] <= col){
        answer++;
        return;
    }

    // 위/왼쪽 보고 가능한 숫자부터 recurse. 세로부터 채움.
    int s = 1;
    if(row > 0) s = max(s, board[row-1][col] + 1); // 위
    if(col > 0) s = max(s, board[row][col-1]); // 왼
    for(int i = s; i<=N; i++){
        board[row][col] = i;
        if(num_col[row+1] > col){ // 아래칸으로 내릴 수 있으면 내리고, 그렇지 않으면 바로 다음 col로 감.
            recurse(row+1, col);
        }
        else{
            recurse(0, col+1);
        }
    }
}

void solve(){
	while(1){
        cin>>k;
        if(cin.eof()) return;

        for(int i = 0; i<8; i++) num_col[i] = 0;
        for(int i = 0; i<8; i++){
            for(int j = 0; j<8; j++){
                board[i][j] = 0;
            }
        }

        for(int i = 0; i<k; i++) cin>>num_col[i];
        cin>>N;
        answer = 0;
        recurse(0, 0);
        cout<<answer<<"\n";
    }
}

//////////////////////

int main(void) {
	cin.tie(0);
	cout.tie(0);
	std::ios_base::sync_with_stdio(0);

	solve();

	return 0;
}

 

 

후기

 이런 purning 문제는 너무 빡세다.