BOJ 1598 : 꼬리를 무는 숫자 나열 (Java/수학/Bronze 3)

---

[문제 링크] 👉 https://www.acmicpc.net/problem/1598

---

설명

원숭이는 두 개의 자연수를 아무거나 생각한다. 그리고 숫자판에서 두 개의 자연수 사이의 직각거리를 구하면 된다.

여기서 직각거리는 동서방향거리와 남북방향거리의 합을 뜻한다.

 

예를 들어 숫자판에서 11과 33을 생각했다고 하자. 그렇다면 11과 33사이의 직각거리는 8이 된다.

(동서방향거리 : 6, 남북방향거리 : 2) 다음 그림에 잘 나타나있다.

 

풀이

입력이 11과 33이라고 하자.

숫자판에서 숫자가 아래로 4개씩, 즉 4의 배수마다 숫자가 나열되기 때문에 4로 나누어줘야 한다.

 

위치 도출 방법

• 11을 4로 나누면 몫은 2, 나머지는 3이다. 이 말은 즉, 11은 2번째 줄 다음줄인 3번째 줄에 나머지가 3이므로 3번째에 있다는 뜻이다. 나머지가 있으면 몫의 다음번째 줄에 있다는 말이고, 나머지가 없으면 몫으로 나온 줄에 있다는 말이다.
• 33도 4로 나누면 몫은 8, 나머지는 1이다. 나머지가 있으므로 (8 + 1) = 9번째 줄의 1번째에 있다고 생각하면 된다. 

 

직각 거리 계산

• 몫을 가로의 거리, 나머지를 세로의 거리라고 생각한다.
• 33의 몫인 8에서 11의 몫인 2를 빼면 가로 거리가 된다. 8 - 2 = 6
• 11의 나머지인 3에서 33의 나머지인 1을 빼면 세로 거리가 된다. 3 - 1 = 2
• 가로 거리와 세로 거리를 더하면 직각 거리가 된다. 6 + 2 = 8

 

그러나 위처럼 단순히 몫과 나머지를 구해서 계산하면 안 된다. 반례가 있기 때문이다. 입력이 5와 4인 경우이다.

5의 몫은 1, 4의 몫은 1이므로 가로 거리는 0이다. 5의 나머지는 1, 4의 나머지는 0이므로 세로 거리는 1이다.

그래서 직각 거리는 1이 된다. 그러나 답은 4이다. 

 

숫자판의 원점을 1부터 시작한다고 가정해서 생긴 오류다. 원점이 0이라고 가정해야 한다. 

따라서 입력 값에 1씩 빼줘야 한다. 

 

 

Solution

import java.io.*;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int num1 = Integer.parseInt(input[0]);
        int num2 = Integer.parseInt(input[1]);
        num1 -= 1; //원점을 0이라 생각하여 1을 빼줌
        num2 -= 1;
        int result = 0;
        result += Math.abs(num1 / 4 - num2 / 4);
        result += Math.abs(num1 % 4 - num2 % 4);

        System.out.println(result);
    }
}

 

 

👩‍💻 회고

풀이를 장황하게 적긴 했지만 좋은 설명은 아닌 것 같다. 단순히 원점을 0이라고 생각하고 -1을 해줬으면 아래와 같이 망한 풀이는 안 나왔을거다. 덜어냄의 미학... 

내 풀이의 허점은 세로 거리를 계산할 때인 것 같다. 가로 거리는 나머지가 있을 때와 없을 때를 구분해서 계산했지만 세로 거리는 따지지 않았던 것이다. 문제를 처음 봤을 때 복잡하게 생각하지 않고 단순히 수학식으로만 직각 거리를 계산해야 한다고 생각한 것까진 잘했는데.. 스스로가 아쉽다. 다음 문제에서는 좀 더 좋은 코드가 나오길!

 

망한 풀이

    //둘 중에 큰 값, 작은 값 분리
        int max = Math.max(num1, num2);
        int min = Math.min(num1, num2);
        //직각거리 계산
        int height = Math.abs((max % 4) - (min % 4)); //나머지 값은 고정
        int width = ((max / 4) + 1) - ((min / 4) + 1); //몫도 빼둠
        if (max % 4 == 0) { //4의 배수면 + 3
            width += 1;
        }
        if (min % 4 == 0) {
            width += 1;
        }
        System.out.println(width + height);

---