글 읽기 - 7%에서 틀렸다고 하네요

16010703 1년 전 0

올라온 반례는 모두 해보았습니다. 논리상 추가적인 반례도 없을 것같고..제 논리를 설명하자면

기본적으로 ㄹ형태로 이동합니다. 만약 R이 짝수면 두줄 남깁니다. 해당 두줄은 ㄹ을 반시계방향으로 돌린 형태로 이동합니다.

그렇게 꼬불꼬불가다가 C가 짝수면 두줄 남깁니다. 결국 2x2가 남고 RD vs DR을 비교해서 진행합니다.

논리적 오류나 반례를 알려주신다면 감사하겠습니다.

(ts 코드로 올립니다)

"use strict";
import readline from "readline";
{
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
  });
  let R = 0;
  let C = 0;
  let r = 0;
  const field: number[][] = [];
  const main = () => {
    const route: string[] = [];
    for (let i = 0; i < field.length - 2; i++) {
      if (i % 2) {
        route.push(Array.from({ length: C - 1 }, () => "L").join(""));
        route.push("D");
      } else {
        route.push(Array.from({ length: C - 1 }, () => "R").join(""));
        route.push("D");
      }
    }
    if (field.length % 2) {
      route.push(Array.from({ length: C - 1 }, () => "L").join(""));
      route.push("D");
      route.push(Array.from({ length: C - 1 }, () => "R").join(""));
    } else {
      for (let i = 0; i < C - 2; i++) {
        if (i % 2) {
          route.push("UR");
        } else {
          route.push("DR");
        }
      }
      if (C % 2) {
        route.push("URD");
      } else {
        if (field[R - 1][C - 2] < field[R - 2][C - 1]) {
          route.push("RD");
        } else {
          route.push("DR");
        }
      }
    }
    console.log(route.join(""));
  };
  rl.on("line", (line) => {
    if (r) {
      field.push(line.split(" ").map((a) => parseInt(a)));
      r--;
      if (r === 0) {
        rl.close();
      }
    } else {
      [R, C] = line.split(" ").map((a) => parseInt(a));
      r = R;
    }
  }).on("close", () => {
    main();
    process.exit();
  });
}

yuris 1년 전 0

R과 C 모두 짝수일 때 [R-1][C]와 [C-1][R]를 제외하는 경우 외에 다른 경로도 가능합니다.

INPUT:
4 4
5 1 5 5
5 5 5 5
5 5 5 5
5 5 5 5

ANS:
DRRURDDLLLDRRR

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

문제

문제

출처

ICPC

7%에서 틀렸다고 하네요

16010703 1년 전 0

yuris 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말