글 읽기 - 어떤 부분이 틀렸을까요 ?

whwoals21 3년 전 0

6중 for 문을 활용하여

첫 씨앗 심고 ->

두번 째 씨앗 심고 ->

세번 째 씨앗 심는

브루트포스 활용했는데 반례 알려주실 수 있나요 ? ㅠ

#include <iostream>

using namespace std;
#define MAX 12

int N, ans = 9999999;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int map[MAX][MAX];
bool been[MAX][MAX];

int min(int a, int b) {
    return a > b ? b : a;
}

void unplant(int x, int y) {
    been[y][x] = false;
    for (int i = 0; i < 4; i++) {
        been[y + dy[i]][x + dx[i]] = false;
    }
}

void plant(int x, int y) {
    been[y][x] = true;
    for (int i = 0; i < 4; i++) {
        been[y + dy[i]][x + dx[i]] = true;
    }
}

int check(int x, int y) { // 씨앗 심을 수 있는지 확인
    int cnt = 0;
    bool flag = false;
    cnt += map[y][x];
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if ((nx < 0 && nx >= N && ny < 0 && ny >= N) || been[ny][nx]) {
            flag = true;
            break;
        }
        cnt += map[ny][nx];
    }

    if (flag) {// 심기 실패
        return -1;
    } else {// 심기 성공
        plant(x, y);
        return cnt;
    }
}

void solve2(int x, int y, int price) { // 세번째 씨앗 심기
    for (int i = y; i < N - 1; i++) {
        for (int j = x; j < N - 1; j++) {
            if (!been[j][i]) {
                int tmp = check(j, i);
                if (tmp != -1) {
                    ans = min(ans, price + tmp);
                    unplant(j, i);
                }
            }
        }
    }
}

void solve1(int x, int y, int price) { // 두번째 씨앗 심기
    // 두번째 씨앗 심기
    for (int i = y; i < N - 1; i++) {
        for (int j = x; j < N - 1; j++) {
            if (!been[j][i]) {
                int tmp = check(j, i);
                if (tmp != -1) {
                    solve2(j, i, price + tmp);
                    unplant(j, i);
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> map[i][j];

    for (int i = 1; i < N - 1; i++) {
        for (int j = 1; j < N - 1; j++) {
            int tmp = check(j, i); // 하나 심고
            solve1(j, i, tmp); // 두번째꺼 심으러 들어감
            unplant(j, i); // 첫번째 심은거 빼주기
        }
    }
    cout << ans << "\n";
    return 0;
}

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

문제

문제

출처

ICPC

어떤 부분이 틀렸을까요 ?

whwoals21 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말