[백준18290] NM과 K (1) (C++)

📌 문제

BOJ 바로가기

N x M 행렬에서 K개의 숫자를 뽑아 합의 최대가 되도록 만드는 문제이다.

🔎 풀이

이상한 착각과 시간초과 때문에 꽤나 고생했던 문제이다.

🥶 처음에는 DFS를 돌릴 때 시간 절약을 위해 i는 x부터, j는 y부터 돌렸다. 다시 말해서 현재 선택한 인덱스부터 돌렸다는 것. 이렇게 했을 때 치명적인 문제는 다음과 같다.

N = 3, M = 3이고 현재 인덱스가 (1, 2)일 때 반복문은 (2, 0)부터 돌아가야 한다. 그러나 실제로는 (2, 2)부터 돌아간다.

해결을 위해 i와 j모두 0부터 시작하도록 수정하였으나... 시간 초과가 떴다. 다른 분들의 반복문도 i, j 모두 0부터 시작하던데 왜 나는 시간 초과가 뜨는가..에 대한 의문이 아직도 풀리지 않았다ㅠ 혹시 문제점을 아시는 분은 댓글 부탁드립니다..!

아무튼 시간 초과를 피하기 위해 i를 x부터 시작하도록 수정하니 맞았습니다를 받을 수 있었다. 확실히 0부터 시작했을 때보다는 시간을 절약할 수 있는 방법이다. 그럼에도 아까의 의문점을 해결하지 못해서 아직 좀 찝찝하긴 하다..

🚩 소스코드

#include <iostream>
using namespace std;

int n, m, k, maximum = -2147483648, num[10][10];
bool visited[10][10] = { false, };

void go(int x, int y, int choice){
    if (choice == k){
        int sum = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if (visited[i][j])
                   sum += num[i][j]; 
            }
        }
        maximum = max(maximum, sum);
        return;
    }
    // 시간초과를 피하기 위해 i는 x부터 시작
    for(int i = x; i < n; i++){
        for(int j = 0; j < m; j++){
            if (!visited[i][j]){
               if (i >= 1 && visited[i - 1][j]) continue;
               if (i < n - 1 && visited[i + 1][j]) continue;
               if (j >= 1 && visited[i][j - 1]) continue;
               if (j < m - 1 && visited[i][j + 1]) continue;
               visited[i][j] = true;
               go(i, j, choice + 1);
               visited[i][j] = false;
            }
        }
    }
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> num[i][j];
    go(0, 0, 0);
    cout << maximum;
}