[editorial] Editorial - H. Kakuro I

  • astein
    astein

    안녕하세요. Astein 입니다.
    1주년 모의고사에 관심을 가져주셔서 감사합니다~
    대회 도중에 문제가 많았지만.. 처음이라 진행이 많이 미숙했다고 너그러이 이해해 주세요 ^^;;
    다음부터는 좀 더 매끄러운 진행을 할 수 있도록 노력하겠습니다.
    그럼 에디토리얼 시작합니다~~ 제가 맡은 문제는 H, I 번 (Kakuro시리즈) 였습니다.

    • 출제의도 처음에 나왔던 문제들의 난이도가 인터넷예선을 준비하기에는 너무너무 높은 문제들밖에 없어서 쉬운 난이도의 문제를 제작해야 겠다고 판단하여, 출제가 결정되었던 Kakuro II (I번) 문제의 output -> input 을 구하는 문제가 탄생하였습니다. 문제 배치는 I번과 나란히 배치하는 것이 문제 이해(?)에 도움이 되리라 생각하여 난이도에 비해 뒤쪽에 배치되었습니다.
    • 문제풀이 사실 이 문제는 특별한 알고리즘이 없습니다. Do it ! 하면 되는 문제니까요. 보드에서 0이 아닌 수가 있으면 그 점을 기준으로 오른쪽으로 살펴보면서 0인 지점에 도달할때까지의 합을 구해서 시작점의 좌표와 함께 리스트에 추가합니다. 이 과정을 마친 다음에는 세로 방향에 대해서도 같은 작업을 해 주면 되지요.
    • WA를 받으신 분들에게 권하는 Check Point
    • 출력의 앞부분에 0/1로 이루어진 보드를 출력해야 하는데 의외로 입력으로 주어진 보드를 그대로 출력하여 틀리는 경우.
    • 문제를 자세히 읽지 않아 출력 순서(가로->세로 / 같은 방향이면 y 정렬)를 지키지 않는 경우.
      • 소스코드 ~~~ cpp

    #include
    #include
    #include
    using namespace std;
    struct elem
    {
    int x, y;
    int rc; // 0 : row, 1 : column
    int sum;
    bool operator < (const elem &a) const
    {
    if (rc == a.rc)
    {
    if (x == a.x)
    {
    return y < a.y;
    }
    return x < a.x;
    }
    return rc < a.rc;
    }
    };
    FILE *in = stdin;
    FILE *out = stdout;
    void solve()
    {
    int N;
    fscanf(in, "%d", &N);
    vector > table(N + 1, vector (N + 1, 0));
    for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
    fscanf(in, "%d", &table[i][j]);
    fprintf(out, "%d\n", N);
    for (int i = 0; i < N; ++i)
    {
    for (int j = 0; j < N; ++j)
    fprintf(out, "%d ", (table[i][j] != 0));
    fprintf(out, "\n");
    }
    elem tmp;
    vector data;
    tmp.rc = 0;
    for (int i = 0; i < N; ++i)
    {
    bool isZero = true;
    for (int j = 0; j <= N; ++j)
    {
    if (table[i][j] != 0)
    {
    if (isZero)
    {
    tmp.x = i + 1, tmp.y = j; tmp.sum = 0;
    }
    isZero = false;
    tmp.sum += table[i][j];
    }
    else
    {
    if (!isZero)
    {
    data.push_back(tmp);
    isZero = true;
    }
    }
    }
    }
    tmp.rc = 1;
    for (int j = 0; j < N; ++j)
    {
    bool isZero = true;
    for (int i = 0; i <= N; ++i)
    {
    if (table[i][j] != 0)
    {
    if (isZero)
    {
    tmp.x = i, tmp.y = j + 1; tmp.sum = 0;
    }
    isZero = false;
    tmp.sum += table[i][j];
    }
    else
    {
    if (!isZero)
    {
    data.push_back(tmp);
    isZero = true;
    }
    }
    }
    }
    fprintf(out, "%d\n", data.size());
    sort(data.begin(), data.end());
    for (int i = 0; i < data.size(); ++i)
    {
    fprintf(out, "%d %d %d %d\n", data[i].x, data[i].y, data[i].rc, data[i].sum);
    }
    }
    int main()
    {
    int T;
    fscanf(in, "%d", &T);
    fprintf(out, "%d\n", T);
    while (T--)
    {
    solve();
    }
    }

    <div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/50055">원문보기</a>]</div>

    13년 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.