[자바] 백준 19953 - 영재의 산책 (java)

목차

문제 : boj19953

 

 

필요 알고리즘

• 정수론, 비둘기집의 원리
  
  • 비둘기집의 원리로 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  실제로 시뮬레이션을 돌려보게 된다면, O(t) 이므로 시간초과가 나게 된다. 따라서 시간을 줄일 아이디어를 찾아야 하는데, 내 경우에 비둘기집의 원리로 시간을 줄였다. n+1마리의 비둘기가 n개의 비둘기집에 들어간다면 자명하게도 최소 1개 이상의 비둘기집은 2마리 이상의 비둘기가 들어가게 된다.

 

  이 문제도 마찬가지인데, 다음 속력은 (v*m)%10 이므로 다음 속력은 0~9의 10가지 경우만 있다. 4방향 모두 각각 t/4번 진행되는데 그 범위가 [0, 9] 이므로 반드시 겹치는 구간이 생긴다. 그리고 동일한 방향에서 겹치는 구간이 생기면, 그 이후로는 반드시 사이클이 발생한다. 따라서 방향 하나를 잡아두고 동일한 속력이 다시 나올 때 까지 돌리면서 몇 번 방향을 바꿨는지 세본다. 많아봐야 40번 내로 동일한 경우가 발생한다. 그럼 해당 사이클 내에 x와 y의 변화량을 측정해두면, t를 해당 값으로 나누어 바로 횟수를 크게 줄일 수 있다.

 

  .. 라고 생각하고 코드를 짰는데, 실제로 돌려보니 첫번째 시도 제외하고 그 이후론 항상 4번 이내로 사이클이 생겼다. 중간 v가 0이었다면 항상 0이고, 중간 v가 5였다면 이후론 항상 5가 뜬다. 그리고 나머지 짝수는 2,4,6,8로 4개이며, 여기에 m이 몇이 되든 항상 짝수가 뜬다. 나머지 홀수는 1,3,7,9이고, 이 경우 m이 홀수라면 1,3,7,9만 뜬다. m이 짝수라면 이후 짝수가 되서 2,4,6,8로 진행되게 되는데 이 때 첫 수는 제외하고 4번 이내이므로 m이 짝수였다면 2번째 수부턴 짝수가 되버린다. 그래서 결론적으로 첫 시도 제외 4번 이내로 가능하다. 그래서 케이스 나눠서 4번 이내로 처리하면 더 효율적으로 짤 수 있다. 아무튼 이하 코드로도 76ms만에(자바론 최소 시간임) 끝났기도 하고 %10이 아니라 다른 수였다면 위 방법이 달라지므로, 이하 코드가 더 범용적이라 생각하여 그냥 패스했다. 물론 귀찮기도 했다. 비둘기집의 원리는 맞다.

 

  아무튼 예를들어 입력이 '13 2 1111' 이라고 해보자. 처음 북쪽으로 갈 때는 v0 만큼 가야 하므로 v가 [0,9] 범위가 아닌 유일한 구간이라 이 부분은 그냥 버린다. 두 번째 v는 (13*2)%10 = 6 이다. 이 때 부터 몇 번 만에 다시 6이 뜨는지 보면, 6 -> 2 -> 4 -> 8 -> 6 으로 4번만에 제자리로 돌아온다. 그렇다면 사이클은 4번만에 생기므로, (1111-1)/4 번에 걸쳐서 동일한 횟수가 반복될꺼다. 1111-1인 이유는 v0은 제외하고 생각했기 때문이다. 그렇다면 사이클이 생기는동안의 x축, y축 변화량을 기록했다가, x = (1110/4) * x축변화량, y = (1110/4) * y축 변화량을 해주면 된다. 이후 남은 횟수인 1110%4 = 2번 만큼은 시뮬레이션으로 돌려주면 된다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
    private static final int MOD = 10;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v0 = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());

        int tmp = (v0*m)%MOD;
        int base = tmp;
        int cnt = 0;
        int y = 0;
        int x = 0;
        for (int i = 0; i < 40; i++) {
            if (i!=0 && i%4 == 0 && tmp == base) break;
            cnt++;

            switch (i%4) {
                case 0: x+=tmp; break;
                case 1: y-=tmp; break;
                case 2: x-=tmp; break;
                case 3: y+=tmp; break;
            }

            tmp = (tmp*m)%MOD;
        }

        int resY = v0;
        int resX = 0;
        t--;
        resY += y * (t/cnt);
        resX += x * (t/cnt);

        for (int i = 0; i < t%cnt; i++) {
            switch (i%4) {
                case 0: resX+=tmp; break;
                case 1: resY-=tmp; break;
                case 2: resX-=tmp; break;
                case 3: resY+=tmp; break;
            }
            tmp = (tmp*m)%MOD;
        }

        System.out.println(resX + " " + resY);
    }
}