글 읽기 - 반례가 있을까요? 대회 tc 는 다 맞습니다.

jkjan 3년 전 0

getNewDeco 함수는

각 장식품을 입력 받아

장식품의 top 과 bottom 을 구합니다.

top 은 위에서 셌을 때의 . 의 개수

bottom 은 아래에서 셌을 때의 . 의 개수입니다.

예를 들어

X..

XX.

XXX

는 top 이 0 1 2, bottom 이 0 0 0 입니다.

그래서 전 장식품의 top 과 현재 장식품의 bottom 중에서

각각의 합 중 가장 최소값만큼 장식품을 밑으로 내릴 수 있습니다.

(합은 두 X 사이의 빈 공간을 말함)

예를 들어 예제의 두번째를 먼저, 첫번째를 그 다음으로 쌓았을 때 각각의 top bottom 을 구하면

4 3 2 1 0

0 0 0 2 2

인데, 여기서 각각 위 아래 합을 구하면 4 3 2 3 2 인데

따라서 최소값이 2 이기 때문에 2칸 내릴 수 있는 것입니다.

그래서 높이는 원래 높이 5에서 2칸 내려서 3만큼 증가합니다.

getMostPushableHeight 함수는 이렇게 최대한 밑으로 내릴 수 있는 높이를 구합니다.

stackNewDeco 함수는

getNewDeco 로 새로운 장식품의 top과 bottom, 원래 높이 를 구하고

getMostPushableHeight 로 밑으로 누를 수 있는 최대 높이를 구한 다음

boxes[*idx], 즉 현재의 박스 높이에 원래 높이 - 누른 높이를 더하고

move 함수로 만약에 박스 높이를 넘었다면 새로운 박스를 준비시킵니다.

copy 함수로 새 장식품의 top을 복사해서 이후 단계로 넘겨줍니다.

그리고 이를 n 번 반복하고

boxes 를 출력해줍니다.

대회 tc 는 다 맞았는데

tc 가 추가된 건지

여기서는 틀렸다고 그러네요.

맞은 사람이 있으니까 물론 제가 틀린 거겠지요

혹시 반례나 오점이 있나요?

지적해주시면 감사하겠습니다.

#include <iostream>
#include <fstream>
#define TOP 0
#define BOTTOM 1
#define MAX_HEIGHT 10
#define MAX_WIDTH 100
using namespace std;
int n, w, b;

void stackNewDeco(int* top, int* boxes, int* idx);

int main() {
    scanf(" %d %d %d", &n, &w, &b);
    int top[MAX_WIDTH] = {0, };
    int boxes[MAX_WIDTH] = {0, };
    int idx = 0;
    for (int i = 0; i < n; ++i) {
        stackNewDeco(top, boxes, &idx);
    }
    idx = 0;
    while (boxes[idx] && idx < MAX_WIDTH) {
        printf("%d ", boxes[idx++]);
    }
    return 0;
}

int getNewDeco(int newDeco[][MAX_WIDTH]) {
    int h;
    scanf(" %d", &h);
    fill(newDeco[TOP], newDeco[TOP] + MAX_WIDTH, h);
    fill(newDeco[BOTTOM], newDeco[BOTTOM] + MAX_WIDTH, h);
    char deco;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            scanf(" %c", &deco);
            if (deco == 'X') {
                newDeco[TOP][j] = min(newDeco[TOP][j], i);
                newDeco[BOTTOM][j] = min(newDeco[BOTTOM][j], h - 1 - i);
            }
        }
    }
    return h;
}

void move(int original, int h, int* boxes, int* idx) {
    if (boxes[*idx] >= b) {
        if (boxes[*idx] > b) {
            boxes[*idx] = boxes[*idx] - h;
            boxes[*idx+1] = original;
        }
        (*idx)++;
    }
}

int getMostPushableHeight(int* top, int* bottom) {
    int mostPushableHeight = MAX_HEIGHT * 2;
    for (int i = 0; i < w; ++i) {
        mostPushableHeight = min(mostPushableHeight, top[i] + bottom[i]);
    }
    return mostPushableHeight;
}

void copy(int* arr1, const int* arr2) {
    for (int i = 0; i < MAX_WIDTH; ++i) {
        arr1[i] = arr2[i];
    }
}

void stackNewDeco(int* top, int* boxes, int* idx) {
    int newDeco[2][MAX_WIDTH];
    int h = getNewDeco(newDeco);
    int mostPushableHeight = getMostPushableHeight(top, newDeco[BOTTOM]);
    int addedHeight = (h - mostPushableHeight);
    boxes[*idx] += addedHeight;
    move(h, addedHeight, boxes, idx);
    copy(top, newDeco[TOP]);
}

clrmt 3년 전 0

4 5 9

.XXXX

XXXXX

X....

klm03025 3년 전 0

@clrmt 문제에서 '모든 장식 판은 두께가 1이고 너비가 모두 같으며' 라고 적혀있습니다.

저 경우에는 너비가 다르기 때문에 잘못된 테케입니다.

clrmt 3년 전 0

앗 지문에 그런 제한이 있었군요.

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

문제

문제

출처

ICPC

반례가 있을까요? 대회 tc 는 다 맞습니다.

jkjan 3년 전 0

clrmt 3년 전 0

klm03025 3년 전 0

clrmt 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말