대메뉴 바로가기 본문 바로가기

데이터 기술 자료

데이터 기술 자료 상세보기
제목 도전! 정보올림피아드 : 개미
등록일 조회수 5105
첨부파일  

도전! 정보올림피아드

개미



매년 5월은 정보올림피아드 시도별 지역본선이 있는 달이다. 정보올림피아드는 미래창조과학부에서 주최하는 대회로 수학적 지식과 논리적 사고능력을 바탕으로 알고리즘과 프로그래밍 능력을 평가하는 대회다. 올해는 32회째로 5월 23일 전국 17개 시도에서 실시된다. 지역본선은 4시간 동안 4~5 문제를 풀게 되는데 작년 대회는 모두 네 문제가 나왔다. 이 중에서 초등부 3번과 중등부 2번 문제였던 ‘개미’문제를 함께 풀어보도록 한다.





개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래그림처럼 왼쪽 아래가 (0, 0) 이고 오른쪽 위가 (w, h) 이다. 이 공간 안의 좌표 (p, q)에 개미 한 마리가 놓여있다. 개미는 오른쪽 위 45도 방향으로 일정한 속력으로 움직이기 시작한다. 처음에 (p, q)에서 출발한 개미는 1시간 후에는 (p+1, q+1)로 옮겨간다. 단, 이 속력으로 움직이다가 경계면에 부딪치면 같은 속력으로 반사되어 움직인다. 위 그림은 6 × 4 격자에서 처음에 (4, 1)에서 출발한 개미가 움직인 길을 보여주고 있다. 처음에 (4, 1)에 있는 개미는 2시간 후에 (6, 3)에 있으며 8시간 후에 (0, 1)에 있다. 만일 그 개미가 처음에 (5, 3)에 있었다면 매 시간마다 (6, 4), (5, 3), (4, 2), (3, 1)로 움직인다.? 여러분은 크기 w × h인 격자 공간에서 처음에 (p, q)에서 출발하는 개미의 t시간 후의 위치 (x, y)를 계산하여 출력해야 한다. 개미는 절대 지치지 않고 같은 속력으로 이동한다고 가정한다. [Input] 첫줄에는 w와 h가 공백을 사이에 두고 주어진다. 그 다음 줄에는 초기 위치의 좌표값 p와 q가 공백을 사이에 두고 주어진다. 3번째 줄에는 개미가 움직일 시간 t가 주어진다. [입력값의 정의역] 2 ≤ w, h ≤ 40,000 0 < p < w 0 < q < h 1 ≤ t ≤ 2,000,000,000 [Sub-Task Info] #1 : w, h < = 3 ; t < = 10 #2 : w, h 중 하나는 1 ; t < = 1,000,000 #3 : t < = 1,000,000 #4 : 추가 제한 사항 없음 [Output] t시간 후에 개미의 위치 좌표 (x, y)의 값 x와 y를 공백을 사이에 두고 출력한다. [IO Example] 입력1 6 4 4 1 8 출력1 0 1 입력2 6 4 5 3 4 출력2 3 1 (출처: koistudy, 2014년 정보올림피아드 지역본선 초등부 3번, 중등부 2번)



평범한 방법

먼저, 문제에 주어진 조건 그대로 구현을 해보자. 개미의 방향은 대각선 방향으로만 움직이므로 오른쪽 위(↗), 오른쪽 아래(↘), 왼쪽 아래(↙), 왼쪽 위(↖), 이렇게 네 개 방향이 존재한다(시계 방향순). 각 방향에 따라 x값, y값의 변하는 정도를 배열해 저장해 놓고, 방향을 정하는 변수를 하나 만들면 보다 간단하게 구현할 수 있다.



<리스트 1> 개미의 방향과 위치 변화를 위한 변수 int d; int dx[4] = {1, 1, -1, -1}; int dy[4] = {1, -1, -1, 1};



<리스트 1>과 같이 설정해 놓은 다음 d의 값을 0부터 3까지 중 하나로 바꿔가면 구현이 쉽다. 개미의 현재 위치 p, q에서 한 시간마다 이동하는 값, 즉 dx[d], dy[d]를 더해 가면서 개미의 위치를 갱신해주면 개미의 최종 위치를 구할 수 있게 된다. 벽에 부딪히는 경우를 만들어 줘야 하는데, d = 0 (오른쪽 위, ↗)이라면 주어진 격자 공간의 오른쪽 끝(w), 또는 위쪽 끝(h), 또는 오른쪽 위 구석(w,h), 이렇게 세 경우에 방향 전환이 발생한다. 오른쪽 끝(w)에 도착했으면 방향을 왼쪽 위(↖, d = 3), 위쪽 끝(h)에 도착했으면 방향을 오른쪽 아래(↘, d = 1), 오른쪽 위 구석(w,h)에 도착했으면 방향을 왼쪽 아래(↙, d = 2)로 각각 변경하면 된다. 같은 방법으로 d가 1부터 3까지 구현하면 프로그램이 완성된다.



<리스트 2> 개미 풀이 1 #include using namespace std; int w, h, p, q, t, d; int dx[4] = {1, 1, -1, -1}; int dy[4] = {1, -1, -1, 1}; int main() { cin >> w >> h >> p >> q >> t; while (t--) { p += dx[d]; q += dy[d]; if (d == 0) { if (p == w && q == h) d = 2; else if (p == w) d = 3; else if (q == h) d = 1; } else if (d == 1) { if (p == w && q == 0) d = 3; else if (p == w) d = 2; else if (q == 0) d = 0; } else if (d == 2) { if (p == 0 && q == 0) d = 0; else if (p == 0) d = 1; else if (q == 0) d = 3; } else if (d == 3) { if (p == 0 && q == h) d = 1; else if (p == 0) d = 0; else if (q == h) d = 2; } } cout < < p < < ' ' < < q < < endl; return 0; }



그런데, <리스트 2>의 프로그램은 아쉽게도 정답이 아니다. 결과값이 틀리지는 않지만 개미의 이동시간이 너무 길기 때문에 제한된 시간(1초) 안에 답을 못 내는 경우가 있다. 문제를 다시 읽어보면 개미의 이동시간 t가 1부터 20억까지로 돼 있다. 채점 서버에 따라 다르지만 보통 정보 올림피아드 대회에서는 1초에 1억 번의 연산이 가능한 것으로 가정하고 프로그램을 작성한다. 따라서 <리스트 2>의 프로그램은 t 값이 대략 1억 미만일 때는 정답을 출력하지만, 1억을 넘게 되면 시간초과(TLE, Time Limit Error)를 받아 문제를 못 푼 것으로 처리된다. 실제 작년 시험에서도 위와 같이 프로그램을 한 경우 100점 만점에 40점만 받도록 테스트 데이터가 구성돼 있었다.

그럼, 어떻게 하면 좀 더 빠르게 결과를 낼 수 있을까? 쉽게 떠오르는 방법은 개미를 1시간 마다 한 칸씩 이동시키지 않고 세 군데 경계 중에서 어디에 부딪힐지를 계산해 한 번에 몇 칸씩 이동하는 방법이다. 이 경우는 프로그램이 좀 더 복잡해지지만 실행속도가 <리스트 2>의 방법에 비해 빠르게 된다. 실제 이 방법으로 구현하면?은 아니다. 좀 더 다른 방법을 생각해 보자.



좀 더 빠른 방법

<리스트 2>의 방법은 t가 20억 이하라는 조건 때문에 시간초과 문제가 생겨 100점을 받을 수 없었다. 시간을 줄이려면 규칙을 찾아야 하는데, 개미의 위치를 X좌표와 Y좌표, 둘로 나누어 보면 의외로 간단한 규칙을 찾을 수 있다.좌표는 벽에 부딪힐 때마다 방향만 바뀔 뿐 항상 일정하게 오른쪽 또는 왼쪽으로 한 칸씩 움직인다. 이것은 나머지 연산자(%)를 이용해 개미의 최종 위치를 쉽게 구할 수 있다는 의미가 된다. 먼저, 개미가 오른쪽으로 무한히 간다고 가정해 보자. 그러면 최종 개미의 x 위치는 p + t가 된다. 여기에서 개미가 몇 차례 왕복을 했는지는 필요 없으므로 x = (p + t) % (2 * w)가 개미의 최종 위치와 관련이 있다. 여기서 w로 나누지 않고 2 * w로 나눈 이유는 개미가 오른쪽으로 가고 있는지, 왼쪽으로 가고 있는지 구분하기 위해서 두 배인 2 * w를 사용했다. 만약 개미가 오른쪽으로 가고 있는 중이었다면 (즉, x가 w보다 작다면) 방금 구했던 x가 그냥 개미의 최종 위치가 된다. 만약 개미가 왼쪽으로 가고 있는 중이었다면 (즉, x가 w보다 크다면) 개미가 마지막으로 오른쪽 벽에 부딪힌 다음에 이동한 것이므로, 2 * w에서 x를 빼준 값이 개미의 최종 위치가 된다. 개미의 최종 X좌표를 프로그램으로 구현한 것은 <리스트 3>과 같다.



<리스트 3> 개미의 최종 X 위치 x = (t + p) % (w * 2); if (x > w) x = 2 * w - x;



개미의 Y좌표도 같은 방법으로 w를 h로 바꾸고, p를 q로 바꿔 구할 수 있다. <리스트 4>는 이를 구현한 것이다. 이 방법은 입력 데이터 크기에 상관없이 개미의 위치를 바로 구할 수 있으므로 시간 복잡도는 O(1)이 된다. 따라서 O(n) 방법이었던 <리스트 2>의 시간초과 문제를 해결하게 되어 100점을 받을 수 있다.



<리스트 4> 개미 풀이 2 #include #include using namespace std; int w, h, p, q, t, x, y; int main() { cin >> w >> h >> p >> q >> t; x = (t + p) % (w * 2); y = (t + q) % (h * 2); if (x > w) x = 2 * w - x; if (y > h) y = 2 * h - y; cout < < x < < " " < < y < < endl; return 0; }



Short Coding

숏코딩은 코드를 가능한 짧게 만드는 것을 말한다. 대회 중에 숏코딩으로 프로그램을 작성하지는 않지만, 시간 날 때 해보면 꽤 재미있다. 위의 개미 문제를 숏코딩으로도 구현해 보자. 우선 #include 대신에 #import를 써서 1바이트를 줄인다. 그리고 그 다음 코드 부분은 사이즈를 줄이기 위해 한 줄에 모두 붙여서 작성한다.



<리스트 5> 개미의 short coding 풀이 #import int w,h,p,q,t;main(){std::cin>>w>>h>>p>>q>>t;p+=t;q+=t;std::cout < < (p/w%2?w-p%w:p%w)< < " "< < ( q/h%2?h-q%h:q%h);}



코드를 짧게 하기 위해 <리스트 4>와는 좀 다르게 작성했는데, 오른쪽으로 가는 중이었는지, 왼쪽으로 가는 중이었는지 판단은 p / w % 2로 했다. p / w를 하면 몫이 나오고 이 몫이 홀수이면 왼쪽으로, 짝수이면 오른쪽으로 가는 것이 된다. 만약 왼쪽으로 가는 중이었다면 w - p % w로 개미의 최종 위치를 구할 수 있고, 오른쪽으로 가는 중이었다면 단순히 p % w가 최종 위치가 된다. 위와 같이 코드를 작성하면 단지 128 바이트의 코드로 개미 문제를 해결할 수 있게 된다.

개미 문제는 경기과학고에서 운영하는 무료사이트인 koistudy(koistudy.net)에서 풀어볼 수 있다. 문제번호는 0413이다.



출처 : 마이크로소프트웨어 5월호

제공 : 데이터전문가 지식포털 DBguide.net