[editorial] 2007년 서울 온사이트 본선 D번 PHONE

  • zizavino
    zizavino

    D번은 참 각별한 인연이 있는 문제입니다. 바로 D가 저의 ICPC 첫 YES입니다 >_<
    D는 휴대폰 자판 하나를 주는데요,(키패드같이 생긴거) 휴대폰 자판 누르는 순서가 정해졌을 때, 손가락에 잉크를 바르고 휴대폰 자판 위로 손가락을 옮겨가며 자취를 만들었을 때, 그 자취를 최소개수의 line segment로 표현해보는 것이 문제입니다.(excellent, good, bad 구분 있는데 별 의미는 없습니다 :) )
    D는 가능한 모든 직선을 고려하는 방법으로 풀 수 있습니다. 즉 모든 기울기를 고려해보는거죠.. 가능한게 얼마 안되는데 가로선, 세로선, (delta 가로, delta 세로) = (+-1, +-2), (+-2, +-1), (+-1, +-3)인 것들만 세보면 됩니다.
    이 때 주의할 점이 하나 있는데, 다른 모든 직선은 여러 line segment가 있으면 하나의 움직임으로 처리할 수 있는 반면(1-2, 2-3은 1-3 한 번으로 되죵~) 2-5, 8-0 하나만 딱 예외입니다. 이 경우를 예외로 처리해서 잘 세면 됩니다.
    대회 초반 시간을 약 15분 잡아먹었던 근성의 코드는 다음과 그다지 다르지 않았습니다. 솔직히 한 번에 Yes 나온게 신기하네요 +_+ 읽어주셔서 감사합니다 :)

    int count(int *arr, int n) {
    int i, ret(0);
    int path[10][10];
    memset(path, 0, sizeof(path));
    for(i = 1; i < n; ++ i) {
        path[arr[i - 1]][arr[i]] = path[arr[i]][arr[i - 1]] = 1;
    }
    if(path[1][2] || path[2][3] || path[1][3]) ++ ret;
    if(path[4][5] || path[5][6] || path[4][6]) ++ ret;
    if(path[7][8] || path[8][9] || path[7][9]) ++ ret;
    if(path[1][4] || path[4][7] || path[1][7]) ++ ret;
    if(path[3][6] || path[6][9] || path[3][9]) ++ ret;
    if(path[5][8] || path[2][8] || path[5][0] || path[2][0]) {
        ++ ret;
    }
    else {
        if(path[2][5]) ++ ret;
        if(path[8][0]) ++ ret;
    }
    if(path[7][0]) ++ ret;
    if(path[4][8]) ++ ret;
    if(path[1][5] || path[5][9] || path[1][9]) ++ ret;
    if(path[2][6]) ++ ret;
    if(path[9][0]) ++ ret;
    if(path[6][8]) ++ ret;
    if(path[3][5] || path[5][7] || path[3][7]) ++ ret;
    if(path[2][4]) ++ ret;
    if(path[1][6]) ++ ret;
    if(path[4][9]) ++ ret;
    if(path[3][4]) ++ ret;
    if(path[6][7]) ++ ret;
    if(path[1][8]) ++ ret;
    if(path[4][0]) ++ ret;
    if(path[2][9]) ++ ret;
    if(path[3][8]) ++ ret;
    if(path[6][0]) ++ ret;
    if(path[2][7]) ++ ret;
    if(path[1][0]) ++ ret;
    if(path[3][0]) ++ ret;
    return ret;
}
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    16년 전
5개의 댓글이 있습니다.
  • 도달도달
    도달도달

    저희도 팀원 한명이 모든 경우의 수를 if로 나누는 노가다로 -_-; 하더니
    1번 WA 나오고 바로 YES 받더군요. 저는 "그런식으로 하면 안된당게"하면서 비난했었는데
    조금 부끄러워졌습니다.


    16년 전 link
  • Toivoa
    Toivoa

    근성의 코드 멋지네요 :) SNUPC에서 제 D 코드(C였나?)를 보는듯한 느낌 -ㅁ-


    16년 전 link
  • astein
    astein

    근데 이 소스엔 치명적인 버그가 있음... "111111111111" => 1이 리턴이 안됨 (AC엔 상관없지만)


    16년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    저도 if문 15개 정도로 짰어요ㅋ


    16년 전 link
  • sooshia
    sooshia

    아주대 the pulza 팀도 28개 가량의 경우의 수를 모두 switch에 박아서 풀었습니다.
    저의 ICPC 첫 YES문제도 이것이네요..ㅜ.ㅜ


    16년 전 link

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