백준 3101 (토끼의 이동) - java

https://www.acmicpc.net/problem/3101

3101번: 토끼의 이동

문제

1부터 N^2까지 수가 지그재그 대각선 순서로 N*N 행렬에 채워져 있다. 아래 그림은 N=6일 때, 행렬의 모습이다.

토끼는 지금 1이 있는 칸에 있다. 토끼는 인접한 칸으로 점프할 수 있다. (위, 아래, 오른쪽, 왼쪽)

토끼가 점프한 방법이 주어졌을 때, 토끼가 방문한 칸에 있는 수의 합을 구하는 프로그램을 작성하시오. 같은 칸을 여러 번 방문할 경우에도, 방문할 때 마다 더해야 한다. 토끼가 행렬을 벗어나는 경우는 없다.

 

유형 : 구현

 

접근 방식

• N의 크기가 100_000이기 때문에 배열을 직접 생성할 경우 메모리 초과가 발생할 것 같다 (물론 안해봄)
• 결국 규칙을 찾아야 하는 문제이다.
  • 해당 문제는 대각선을 중심으로 바라봐야 한다. 1이 있는 칸을 첫 번째 대각선이라 정의하겠다. 대각선의 개수는 2N -1개이다.
  • 대각선이 홀수번인지 짝수번인지에 따라 다른 규칙이 적용된다.
    • 홀수번 : 왼쪽 아래부터 숫자가 증가
    • 짝수번 : 오른쪽 상단부터 숫자가 증가
  • 각 대각선의 시작 숫자는 N+1까지를 기점으로 2가지로 나뉜다.
    • 1 ~ N+1까지
      • 전 대각선의 시작 숫자에서 (전값에 1씩 증가한 순차 번호)로 증가한다. (1 - 2 - 3 - 4 .... N)
    • N+1 ~ 2N -1
      • 전 대각선의 시작 숫자에서 (전값에 1씩 감소한 순차 번호)로 증가한다. (N-1 , N-2, 2 , 1)
  • 우리는 이동한 위치의 행과 열의 숫자를 합하여 해당 위치의 대각선 번호를 알 수 있다.
    • (0,0)부터 시작인 경우 row + cal + 1 = 대각선 번호
• 찾은 규칙들을 바탕으로 다음 위치의 값을 구할 수 있다. 숫자가 크기 때문에 long 타입으로 결과를 계속 갱신해나가자 !

이동한 위치의 대각선 번호를 찾고 시작 번호로부터 현재 위치의 값을 도출 (코드에 규칙을 정의해놈) , 이전 값에 해당 값을 더해서 결과를 도출

 

전체 코드

package Implementation_BruteForce;
import java.io.*;
import java.util.*;

public class BOJ_3101_토끼의_이동 {
    static int n = 0;
    static int k = 0;

    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0}; // 4방 이동

    static long[] startNum; // 각 줄의 시작
    static int curX = 0; static int curY = 0; // 위치

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        char[] move = br.readLine().toCharArray();

        startNum = new long[2*n+2];

        // 각 줄의 시작 숫자를 저장. 여기서 줄이란 대각선을 의미한다. 1부터 시작한다 가정
        startNum[1] = 1;

        int idx = 1;

        // n+1번째 대각선까지 시작 숫자는 전 숫자에 순차적으로 증가하는 idx값 만큼 증가한다. (idx : 1 , 2 , 3 ,4 , 5 , n)
        for(int i=2 ; i <= n;i++){
            startNum[i] = startNum[i-1] + idx++;
        }

        // n+2번째 대각선부터 끝까지는 idx값이 반대로 감소한다. (idx : n-1 , n-2 , ... 2, 1)
        for(int i=n+1; i <= 2*n-1; i++){
            startNum[i] = startNum[i-1] + idx--;
        }

        // 최종 결과
        long result = 1;


        for(int i = 0 ; i < k ; i++){
            char curMove = move[i];
            // R L U D
            if(curMove == 'D'){
                curX += dx[3];
                curY += dy[3];
            }else if(curMove == 'R'){
                curX += dx[0];
                curY += dy[0];
            }else if(curMove == 'L'){
                curX += dx[1];
                curY += dy[1];
            }else{
                curX += dx[2];
                curY += dy[2];
            }

            int totalNum = curX + curY;

            // 행과 열을 합한 숫자에 1을 더한 값이 해당 '대각선의 순번'이다
            long curStart = startNum[totalNum + 1];

            if(totalNum % 2 == 0){
                // 짝수 라인
                if(totalNum < n ){
                    result += curStart + curY;
                }else{
                    result += curStart + Math.abs(n - curX - 1);
                }

            }else{
                // 홀수 라인
                if(totalNum < n){
                    result += curStart + curX;
                }else{
                    result += curStart + Math.abs(n - curY - 1);
                }
            }
        }

        System.out.println(result);
        br.close();
    }
}