DIAMOND문제 채점에서 의심가는 부분을 발견했습니다

  • wjy721
    wjy721

    안녕하세요

    DIAMOND문제 풀면서 여러가지 소스를 제출해보면서
    특정 입력에 대해 오답이 뜨는 소스코드도 "정답" 판정을 받아서 질문 드립니다.

    아래의 입력
    3
    ..#..
    .#.#.
    ..#..
    에 대한 정답은 1입니다.

    그런데, 위의 입력에 대해서 3을 출력하는 소스215729를 제출해서 정답 판정을 받았습니다.
    반면에 위의 입력에 대해 1을 출력하는 소스는 오답 판정을 받았네요.

    제가 문제를 해결한 방식은,

    2차원 벡터 vector < vector < int > > cache를 선언하고

    cache[y][x] == "(x,y)에 있는 #을 다이아몬드의 가장 아래쪽으로 기준 삼았을때, 만들 수 있는 가장 큰 다이아몬드의 크기"로 정의하고 아래의 점화식을 세웠습니다.

    　　　　…　　　
    　　　　ⓒ　　　
    　…　ⓐ＃ⓑ　…
    　　…　？　…　

    위 그림에서 ？위치를 (x, y)라고 했을 때,
    cache[y][x] = min( cache[y-1][x-1], cache[y-1][x+1], cache[y-2][x] ) + 2;
    　　　　　　　　　　　　ⓐ　　　　　　　　　ⓑ　　　　　　ⓒ

    여기서, ？위치의 바로 윗칸에는 반드시 #이 있어야하므로,
    해당 칸에 있는 문자가 '.'일 경우, 반복문을 건너뛰는 아래의 소스를 추가하였습니다.

    if (table[y - 1][x] == '.') continue;

    ？윗 칸이 무엇인지 확인하는 위의 코드를 삽입한 소스215728는 오답을 받았고,
    위의 코드를 주석처리한 코드215729는 정답을 받았습니다.

    제가 생각하기에 채점 데이터에 문제가 있는것 같아서 질문 남겨드립니다.
    감사합니다.


    10년 전
3개의 댓글이 있습니다.
  • astein
    astein

    채점 데이터가 모든 케이스를 커버하는 것은 아니기 때문에 잘못된 코드로도 정답 판정을 받을 수 있긴 합니다... :)


    10년 전 link
  • astein
    astein

    아래의 데이터에서 문제가 있는 것 같습니다.

    8
    .#.
    ###
    .#.
    ...
    ...
    .#.
    ###
    .#.


    10년 전 link
  • wjy721
    wjy721

    제가 생각했던 코드 한 줄에 문제가 있는게 아니라 전혀 다른곳에 문제가 있었네요... 답변 감사합니다!


    10년 전 link

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