백준 3101번: 토끼의 이동(Python/Java)

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

3101번: 토끼의 이동

 

 

 

접근

---

이 문제의 중요 포인트는 '현재 토끼가 서있는 칸의 숫자'를 어떻게 찾아내냐는 것이다. 다들 알고리즘 문제를 풀며 생긴 소위 '짬바'가 있으니 벌써 감이 잡혔겠지만, 직접 표의 모든 부분을 구현하려고 하면 당연하게도 시간(혹은 메모리) 초과가 뜰 것이다. 최대 길이가 100,000이니 최대 길이로 문제가 나온다면 이에 따른 칸 수는 10,000,000,000개가 된다. 백억 개의 칸을 모두 직접 채운다고 생각하면 너무 당연한 결과일 것이다. 그렇다면 자연스럽게도 이 문제는 각 칸에 들어가는 숫자의 규칙을 찾는 문제가 된다. 문제 예시인 6*6 행렬을 살펴보자.

 

 

문제에서 나왔던 행렬에 인덱스를 함께 써준 것이다. (물론 0, 0부터 시작하는 것이 맞지만 이번 문제를 풀 때에는 개인적으로 1, 1이 편했기 때문에 첫 번째 칸의 인덱스를 1, 1로 정하고 풀었다.) 우리는 여기서 두 가지만 알면 해당 칸의 숫자를 알 수 있다. 바로 현재 토끼가 있는 칸이 몇 번째 대각선 줄에 속해있는지, 그리고 그 대각선 줄에서 몇 번째 칸인지. 대각선 번호가 중요한 이유는 대각선 번호를 통해 현재 선이 시작될 때까지 쓰인 숫자를 알 수 있기 때문이다. 대각선 줄에서 몇 번째 칸인지 중요한 이유는 대각선 줄 내에서의 번호와 현재 선이 시작될 때까지 쓰인 숫자를 더하면 현재 칸에 쓰여 있는 숫자가 되기 때문이다.

 

각 대각선 숫자들의 특징이 무엇인지 감이 오는가? 감이 잘 오지 않는다면 위 그림의 표에 쓰여있는 인덱스와 잘 비교해 살펴보자. 괜히 민망해서 감이 온 척하는 사람들을 위해 빠르게 정답을 말하자면 높이 인덱스와 너비 인덱스를 합한 값에 1을 빼준 값이 각 대각선의 번호가 된다. 예를 들어 3, 2 인덱스는 4번째 대각선에 속한다. 그렇다면 이제 해당 대각선 줄 내에서 몇 번째 칸인지 확인하는 방법을 알아보자.

 

이때는 두 가지 방법으로 나눠서 생각해봐야 한다. 첫 번째 대각선부터 가장 가운데 대각선(위 경우에는 6번)까지는 높이 인덱스가 몇 번째 칸인지 알려준다. 그러나 그 이후부터는 높이 인덱스가 유동적으로 변한다. 사람마다 구하는 방법이 다를 순 있지만, 나 같은 경우는 높이 인덱스에서 (대각선 순번 - 배열 한 변의 길이)를 뺀 값을 통해 알아냈다.

 

여기서 대각선 번호가 짝수인지, 홀수 인지도 나눠서 생각해야 한다. 짝수번일 때에는 위에서 아래로, 홀수번일 때에는 아래에서 위로 칸의 숫자가 상승하기 때문이다.

 

중요한 구현 내용은 여기까지다. 여기까지 잘 따라왔으면 나머지 자잘한 구현들 또한 쉽게 구현할 수 있을 것이다. 한 가지 팁을 주자면 가장 가운데 대각선보다 번호가 큰 대각선들의 각 칸 숫자를 찾는 부분에서 주의를 기울이면 더 쉽게 풀 수 있을 것이다.

 

 

 

풀이

---

Python

length, turn = map(int, input().split())
testCase = list(input())

upDown = [1, 0, -1, 0, 0]
leftRight = [0, 0, 0, -1, 1]

thisLocation = [1, 1]
result = 1
for i in testCase:
    
    thisLocation[0] += upDown[(ord(i)-68)%5]
    thisLocation[1] += leftRight[(ord(i)-68)%5]

    lineNum = ((thisLocation[0] + thisLocation[1]) - 1)
    if lineNum < (length+1):
        lineStart = ((lineNum*(lineNum-1)//2))
        if lineNum%2 == 0:
            result += (lineStart + thisLocation[0])
        else:
            result += (lineStart + (lineNum-(thisLocation[0]-1)))

    else:
        thisNum = (2*length-lineNum)
        lineStart = ((length*(length+1))//2) + ((length*(length-1))//2 - (thisNum+1)*thisNum//2)
        subLocation = (thisLocation[0] - (lineNum-length))
        if lineNum%2 == 0:
            result += (lineStart + subLocation)
        else:
            result += (lineStart + (thisNum-(subLocation-1)))

print(result)

 

Java

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        String[] firstLine = (scan.nextLine()).split(" ");
        long length = Integer.parseInt(firstLine[0]);
        long turn = Integer.parseInt(firstLine[1]);

        String[] testCase = (scan.nextLine()).split("");

        long[] upDown = {1, 0, -1, 0, 0};
        long[] leftRight = {0, 0, 0, -1, 1};

        long[] thisLocation = {1, 1};
        long result = 1;
        for(String i: testCase){

            thisLocation[0] += upDown[((int)i.charAt(0)-68)%5];
            thisLocation[1] += leftRight[((int)i.charAt(0)-68)%5];

            long lineNum = ((thisLocation[0] + thisLocation[1]) - 1);
            if(lineNum < (length+1)){
                long lineStart = ((lineNum*(lineNum-1)/2));
                if(lineNum%2 == 0){
                    result += (lineStart + thisLocation[0]);
                }else{
                    result += (lineStart +(lineNum-(thisLocation[0]-1)));
                }
            
            }else{
                long thisNum = (2*length-lineNum);
                long lineStart = ((length*(length+1))/2) + ((length*(length-1))/2 - (thisNum+1)*thisNum/2);
                long subLocation = (thisLocation[0] - (lineNum-length));
                if(lineNum%2 == 0){
                    result += (lineStart + subLocation);
                }else{
                    result += (lineStart + (thisNum-(subLocation-1)));
                }
            }

        }

        System.out.println(result);

    }

}

 

 

 

후기

---

규칙을 찾느라 조금 애먹었던 문제. 하지만 예시 배열의 인덱스를 자세히 살펴보니 생각보다 그 규칙을 쉽게 찾을 수 있었다. 지난번에도 느꼈지만, 어느 정도 단순한 부분에서는 직접 작성해서 보는 것도 하나의 방법이 될 수 있다는 것을 항상 생각해두자.

 

또, 문제를 볼 때 너무 당연하게도 규칙이 존재할 것이라고 보이는 문제들이 있다. 범위가 작을 때면 규칙을 구해서 답을 찾기보다는 직접 구현하는 방식을 사용하곤 했다. 그게 더 편한 것은 사실이니까. 그런데 그러다 보니 실제 규칙을 구해야만 풀 수 있는 문제들을 풀 때, 규칙을 찾고 구현하는 힘이 부족한 게 느껴질 때가 있다. 직접 구현하며 규칙을 찾는 연습을 덜하게 된 결과라고 생각한다. 앞으로는 범위가 작은 문제라도 직접 규칙을 찾아서 문제를 해결하도록 노력해야겠다.