gimmesilver's blog

Agbird.egloos.com

포토로그



나이 들면 못 푸는 정보 올림피아드 문제 프로그래밍

 일단 문제에 대한 설명은 충격과 공포의 올림피아드 예선문제 를 참조하시고...

 어제 저 블로그 글을 본 우리 팀의 jay님이 역시 같은 팀의 한 알고리즘하는 araste님에게 저 문제에 대한 조언을 구했다. "저 문제...출제자가 5분안에 풀수 있다고 했다던데 님 생각은 어떠삼?" 그러자 araste님 왈..."아휴 이런 문제는 대학생이상되는 나이 많은 사람은 빨리 못 풀어요..." 여기에 심하게 상처받은 우리 팀...그 이후 좀 복잡한 코딩 들어가면 모두들 '아아 나이가 너무 들어서 이런 복잡한 건 못 하겠어...' 라고 중얼거리고 있다는...

 암튼 araste님이 제시한 해법은 각 사각형의 꼭지점 및 사각형간의 교차점을 먼저 구한 후 x축을 기준으로 스캐닝하듯 쭉 훑으면서 사각형의 시작과 끝이 되는 꼭지점 및 교차점을 만날 때 마다 사각형 영역 정보를 관리하면 된단다...

 내 경우는 저 문제를 색칠 공부와 집합에 대한 메타포를 이용해서 풀었다. 주어진 사각형을 각각 다른 색깔의 크레파스로 색칠한다고 생각해보자. 그러면 중첩된 부분은 두 색이 겹치면서 다른 색이 칠해질 것이다. 결국 색칠을 끝낸 후 색깔들의 가짓수가 나눠진 영역의 갯수가 된다. 이제 도형을 해당 영역내에 포함된 좌표들의 집합이라고 생각해보자. 그러면 집합에 포함된 원소들의 갯수가 곧 도형의 넓이가 된다.

 이제 위의 아이디어를 바탕으로 자바를 이용해서 소스를 작성해 보면 아래와 같다. 

import java.util.*;
import java.util.Map.Entry;

public class ColorPainting {
    private static final class Point {
        final int x;
        final int y;
        public Point(int x, int y) {
            this.x = x; this.y = y;
        }

        @Override public String toString() { return "("+x+","+y+")"; }
        @Override public boolean equals(Object o) { return o instanceof Point
            && (this.x == ((Point)o).x && this.y == ((Point)o).y); }
        @Override public int hashCode() { return x+y; }
    }

    private static List<Point> getPointSetFromBox(Point leftTop, Point rightBottom) {
        List
<Point> set = new ArrayList<Point>();
        for (int i = leftTop.x; i < rightBottom.x; ++i) {
            for (int j = leftTop.y; j > rightBottom.y; --j)
                set.add(new Point(i, j));
        }
        return set;
    }

    private static void paintBox(Map<Point,List<Integer>> boxes, Point lt, Point rb, int color) {
        List<Point> ret = getPointSetFromBox(lt, rb);
        for (Point p : ret) {
            List<Integer> val = boxes.get(p);
            if (val == null) {
                val = new ArrayList<Integer>
();
                boxes.put(p, val);
            }
            val.add(color);
        }
    }

    private static Map<List<Integer>, List<Point>> createFigureMap(Map<Point,List<Integer>> boxes) {
        Map<List<Integer>,List<Point>> ret = new HashMap<List<Integer>,List<Point>>();
        for (Entry<Point,List<Integer>> entry : boxes.entrySet()) {
            List<Point> val = ret.get(entry.getValue());
            if (val == null) {
                val = new ArrayList<Point>
();
                ret.put(entry.getValue(), val);
            }
            val.add(entry.getKey());
        }
        return ret;
    }   

    public static void main(String[] args) {
        Map<Point,List<Integer>> boxes = new HashMap<Point,List<Integer>>();
        Point[] leftTops = { new Point(2,6), new Point(4,9), new Point(5,5) };
        Point[] rightBottoms = { new Point(6,2), new Point(9,4), new Point(8,3) };

        for (int color = 0; color < leftTops.length; ++color) {
            paintBox(boxes, leftTops[color], rightBottoms[color], color);
        }

        Map<List<Integer>, List<Point>> ret = createFigureMap(boxes);

        Entry<List<Integer>, List<Point>> maxFigure = Collections.max(ret.entrySet(), new Comparator<Entry<List<Integer>,List<Point>>>() {
            public int compare(Entry<List<Integer>,List<Point>> o1, Entry<List<Integer>, List<Point>> o2) {
                return o1.getValue().size() - o2.getValue().size();
            }
        });

        System.out.println("total figure count: " + ret.size() + ", max figure size: " + maxFigure.getValue().size());
    }
}


 p.s. 물론 나도 5분 안에 풀진 못했다. 어제 친구 만나러 가는 길에 아이디어가 생각났고 오늘 아침에 회사와서 구현해본거니...반나절 걸린건가...-_-a


덧글

  • 지민아빠 2008/06/24 13:54 # 삭제 답글

    아아 이걸 직접 풀어보신거에요? 저는 저자직강 해설을 듣고도 별로 풀고 싶은 마음이 안들던데.. 역시 나이가 들어서 그런건가... ㅎㅎ
  • silverbird 2008/06/24 16:26 #

    아휴 이런 문제는 애 아빠는 별로 풀고 싶은 마음이 안 생겨요... -_-
  • 2008/06/24 18:55 # 삭제 답글 비공개

    비공개 덧글입니다.
  • 백승우 2008/06/24 20:13 # 답글

    itoa도 구현하기 싫어 위키본 1人 ... - -;

    이거 단위 사각형을 만든다음에 2번 겹치는 횟수를 구하고 N개의 사각형 갯수를 더하면 ...... 더하면... 더하면 ..
    아마도 maybe.. 나올듯..
    (퇴근준비중이라.. 코드는 안봤어요..)
  • silverbird 2008/06/24 21:13 #

    2번이상도 겹칠 수 있다는 점만 유념하신다면 말씀하신 방법을 조금만 세부적으로 기술하면 됩니다.
  • jick 2008/06/25 09:57 # 삭제 답글

    안녕하세요... 아트레유입니다. 트랙백 걸어주신 덕분에 어제 블로그 접속자가 폭증해서 즐거워하고 있습니다. :P jay 씨에게 안부 전해주세요~

    그나저나 출제자가 5분만에 풀어야 운운한 건 그냥 심심해서 뻘소리한 건데 -_- 그걸 다들 그렇게 진지하게 받아들이시다니... -_-;;; 하여튼 본의 아니게 출제자를 음해(?)하게 된 것에 대하여 심심한 사과의 말씀을 드립니다.
  • silverbird 2008/06/25 14:17 #

    제가 좀 소심해요...-_-a

    p.s. 아 근데 원래 jay님과 아는 사이셨군요...^^;
  • 짱구엄마 2008/06/25 11:04 # 삭제 답글

    이런 걸 구현한 님도 범상치 않으세횻~ 어린 천재한테 안 밀리려면 이런것도 해야하나...훌쩍...님 힘내세욤
  • silverbird 2008/06/25 14:17 #

    저 알고보면 범상해요...-_-a
  • corba 2008/07/01 10:48 # 삭제 답글

    요즘 고등학생들 푸는 문제 꽤 어려운거 같아요 ㅠㅠ
    옛날에 고등부 문제를 연대대학원생들이 못풀었다는 얘기를 들은 기억이 있다는 ;;;

    늙으면 죽어야 하나... OTL
  • silverbird 2008/07/01 19:30 #

    대신 고딩들은 대학원생 문제를 못 풀거라는...-_-
  • cw 2010/05/27 21:09 # 삭제 답글

    색종이 문제네요 ㅋㅋㅋㅋㅋ
  • 유령 2012/01/18 02:08 # 삭제 답글

    92학번이라.. 좀 나이가 들었나요?
    제목이 과격하여.. 자세히 읽어 보다보니.. 헉, 무슨 소린지..

    그러다, 색을 칠하면 된다는 아이디어를 보고..
    배열을 이용하여 c로 코딩하였더니, 음.. 30분 정도 걸리네요.
    아무런 알고리즘도 없이, 그냥 무식하게 for문만 디립다 사용하여서.. 속도는 자신못하지만.. ㅋㅋ

    요즘 학생들은 이런 문제도 푼다는 건가요? 오~~ 대단해요.
    그런데, 내가 보았던 신입들은 이런 문제를 풀수 있었던.. (쿨럭~~)

    PS. 다음처럼 소스중 일부를 변경하면 답이 total figure count: 6, max figure size: 4 로 나옵니다.
    Point[] leftTops = { new Point(1,4), new Point(2,5), new Point(3,5) };
    Point[] rightBottoms = { new Point(6,3), new Point(5,2), new Point(4,1) };
    물론 내 프로그램도.. 그런데, 이게 맞는 건가?
    영역의 개념이 뭐지? 아 어러워~~
댓글 입력 영역