글 읽기 - 14391 종이 조각 반례

qodydgk8624 1년 전 0

안녕하세요. 질문에 올라온 모든 반례를 비롯해서 다 확인하고, 추가적으로 스스로 반례를 만들어 보기도 하였으나 반나절째 해결이 안되어 질문을 남겨봅니다. 반례를 찾아주시면 감사하겠습니다..

비트마스킹으로 풀어야 하는 것이 속도 측면에서 더 뛰어나지만, 쓰지 않고도 또는 쓰고도 다 해보고 싶어 시도하고 있지만 현재 "시간초과"가 아닌 "틀렸습니다" 가 발생합니다.

// BOJ - 14391 종이 조각

#include <bits/stdc++.h>
#define loop(i, s, n) for(int i = s; i <= n; i++)
#define LOOP(i, s, n) for(int i = s; i < n; i++)
 
using namespace std;

int n = 0, m = 0, arr[4][4] = {0, }, visited[4][4] = {0, }, ans = 0;

int dx[7] = {0, 0, 0, 0, 1, 2, 3};
int dy[7] = {3, 2, 1, 0, 0, 0, 0};

void set_visited(int x, int y, int nx, int ny, int cnt) {
    // (x, y) 부터 시작해서 (nx, ny) 까지 visited를 cnt로 업데이트하는 함수입니다.
    while(1) {
        visited[x][y] = cnt;
        if(x == nx && y == ny) return;
        x += !!(nx - x); y += !!(ny - y);
    }
    return;
}

void calc() {
    vector<int> nums(17, 0); int max_nums = 0;
    LOOP(i, 0, n) LOOP(j, 0, m) {
        max_nums = max(max_nums, visited[i][j]);
        nums[visited[i][j]] = 10 * nums[visited[i][j]] + arr[i][j];
    }
    int _sum = 0;
    loop(i, 1, max_nums) _sum += nums[i];

    ans = max(ans, _sum);
    return;
}

void dfs(int x, int y, int cnt) {
    if(x == n) { // 끝까지 도달
        calc(); return;
    }
    if(visited[x][y]) { // 방문했다면, 다음 숫자로 넘김.
        y = (y + 1) % m; // 다음 줄로 넘어갔으면, y는 0 이어야 함.
        x += !y; dfs(x, y, cnt);
        return;
    }
    LOOP(i, 0, 7) {
        int nx = x + dx[i], ny = y + dy[i];
        if(!(nx < n && ny < m)) continue;
        if(visited[nx][ny]) continue;
        
        set_visited(x, y, nx, ny, cnt);
        dfs(x, y, cnt + 1);
        set_visited(x, y, nx, ny, 0);
    }
    return;
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    
    cin >> n >> m;
    LOOP(i, 0, n) {
        string ss; cin >> ss;
        LOOP(j, 0, m) arr[i][j] = ss[j] - '0';
    }
    
    dfs(0, 0, 1);

    cout << ans << '\n';

    return 0;
}

qodydgk8624 1년 전 0

49번째 줄에서, (x, y) -> (nx, ny) 까지 방문했는지 확인해야 하는데, (nx, ny) 만 확인해서 생긴 문제 였습니다.

풀었습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

14391 종이 조각 반례

qodydgk8624 1년 전 0

qodydgk8624 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말