[자바] 백준 3101 - 토끼의 이동 (java)

 문제 : boj3101

---

 

필요 알고리즘 개념

• 수학, 구현
  
  • 수학태그가 달려있긴한데, 약간의 규칙찾기 + 구현 문제인 것 같다.

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

 

---

 

풀이

   대각선으로 지그재그로 작성된걸 잘 살펴봐보자. 1 -> 2 -> 4 -> 7 -> 11 -> 16 까지 등차수열처럼 증가한다.(증가비가 1, 2, 3,...) 그리고 36 -> 34 -> 31 -> 27 -> 22 에서 등차수열처럼 감소한다.(감소비가 2, 3, 4, ...) 

 

  그럼 대강 현재 위치가 어떤 대각선 위치에 있는지 알고 있고, 시작점의 수만 알고 있다면 상당히 간단해보인다. 규칙성을 더 찾아보자.

좌표 위치를 (r, c) 로 표현해보자. 시작위치는 (0, 0)이고, 거기서 아래로 내려오면 (1, 0)이 되는 식이다. 즉, U=r--, D=r++, L=c--, R=c++ 이다. 그럼 3X3 배열에서 생각해보면 r+c 가 좌측 상단부터 우측 하단까지 대각선을 수평으로 그린다고 했을 때(아래 그림의 색상처럼), 몇 번 대각선에 포함되는 지점인지 알 수 있게 해준다. 예를들어 (1,1)은 r+c = 2 이고, 실제로 3번째 대각선에 포함된다(인덱스로는 2). 

 

  그리고 위 이미지에서 n=3일 때, 대각선의 수는 2n-1개 임을 알 수 있다. 그리고 대각선 n개까지는 r 또는 c가 0임을 볼 수 있는데, 그렇다면 r+c가 홀수이냐 짝수이냐에 따라서 해당 대각선의 시작 값 + r 또는 c를 통해 값을 파악할 수 있음을 알 수 있다. 예를들어 이하 이미지에서 '8'이 써져있는 칸은 (1,2)이고, 1+2로 인덱스 3에 해당하는 대각선 위치임을 알 수 있다. 그리고 r+c가 홀수이므로 우측상단에서 좌측하단으로 내려오는 대각선임을 알 수 있고, 따라서 해당 대각선의 시작 값(7) + r 로 답을 구할 수 있다.

 

  대각선 n개 이후로는 어떻게 알 수 있을까? (1,2), (2,2) 이런게 보이는데, 역방향이므로 (n-1-r, n-1-c)로 생각하면 된다. 즉 변경해보면 (1,0), (0,0)이 된다. 그리고 위와 마찬가지의 규칙을 적용하면 되는데 이번엔 홀수일 때 n-1-c를 더해주면 된다.

 

  설명하기가 상당히 난감한데, 직접 그려보고 위에 말한대로 규칙성을 찾아보면 바로 보일 것이다. 매번 등차수열의 합 공식을 사용해 대각선 인덱스에 따른 시작지점 값을 알아내도 될 것 같지만, 난 수학에 약하므로 2n-1개의 배열 base를 만들어서 미리 각 대각선의 시작 값을 계산해두었다.

public void solution(int n, int k, String str) throws Exception {
    long[] base = new long[2*n-1];	// 미리 대각선 idx에 따른 시작 값 계산
    base[0] = 1;
    for (int i = 1; i < n; i++) {	//(0,0)부터 등차수열 형태로 증가
        base[i] = base[i-1] + i;
    }
    base[2*n-2] = 1l*n*n;
    for (int i = 2; i < n; i++) {	//(n-1,n-1)부터 등차수열 형태로 감소
        base[2*n-1-i] = base[2*n-i] - i;
    }

    int r = 0;
    int c = 0;
    long sum = 1;
    for (int i = 0; i < k; i++) {
        switch (str.charAt(i)) {	// 다음 좌표 계산
            case 'U': r--; break;
            case 'D': r++; break;
            case 'L': c--; break;
            case 'R': c++; break;
        }
        sum += base[r+c] + getWeight(n, r, c);	// base[r+c]로 우선 대각선 시작값을 넣고
    }
    System.out.println(sum);
}

private int getWeight(int n, int r, int c) {	// 이걸로 설명한대로 가중치(r+c의 홀짝에 따라 r을 쓸건지 c를 쓸건지) 계산
    if (r+c >= n) {
        r = n-1-r;
        c = n-1-c;
        int tmp = r;
        r = c;
        c = tmp;
    }
    return (r+c)%2==0 ? c : r;
}

 

---

 

코드 : github

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

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        String str = br.readLine();
        new Main().solution(n, k, str);
    }

    public void solution(int n, int k, String str) throws Exception {
        long[] base = new long[2*n-1];
        base[0] = 1;
        for (int i = 1; i < n; i++) {
            base[i] = base[i-1] + i;
        }
        base[2*n-2] = 1l*n*n;
        for (int i = 2; i < n; i++) {
            base[2*n-1-i] = base[2*n-i] - i;
        }

        int r = 0;
        int c = 0;
        long sum = 1;
        for (int i = 0; i < k; i++) {
            switch (str.charAt(i)) {
                case 'U': r--; break;
                case 'D': r++; break;
                case 'L': c--; break;
                case 'R': c++; break;
            }
            sum += base[r+c] + getWeight(n, r, c);
        }
        System.out.println(sum);
    }

    private int getWeight(int n, int r, int c) {
        if (r+c >= n) {
            r = n-1-r;
            c = n-1-c;
            int tmp = r;
            r = c;
            c = tmp;
        }
        return (r+c)%2==0 ? c : r;
    }
}