[백준] 1022번 Java (수학, 구현)

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

💡문제

💡풀이

접근법: 양쪽 대각선으로 네 부분으로 나눈다. (상하좌우)

그림판으로 최선이었다..

5*5의 소용돌이 숫자들을 그리고 알아보자
중간에 있는 수 1(0,0)에서 오른쪽 아래로 가는 대각선이 1, 9, 25로 증가하는 것을 볼 수 있다.

1 주위를 둘러싼 8개의 숫자들을 한 껍데기라고 하면,
1번째 껍데기는 1, 2번째 껍데기는 2~9, 3번째 껍데기는 10~25의 숫자들이 있다.

각 껍데기의 마지막 숫자가 1의 제곱, 3의 제곱, 5의 제곱으로 늘어나므로
n번째 껍데기의 마지막 숫자는 (2n-1)(2*n-1)이 될 것이다.
즉 n+1번째 껍데기의 첫번째 숫자는 (2n-1)(2*n-1)+1 이다.

이를 토대로 큰 대각선을 두개 그리고 각각 오른쪽, 위, 왼쪽, 아래로 나누면
깊이와 x,y 값에 따라 소용돌이 숫자를 구할 수 있다.

 static int spinalNumber(int x, int y){
        int depth = Math.max(Math.abs(x), Math.abs(y));
        
        // 이전 depth의 마지막 수
        int startNumber = (2*depth-1)*(2*depth-1);

        if(x == depth){
            return startNumber + depth*7 + y;   //아래
        }else if(y == -depth){
            return startNumber + depth*5 + x;   //왼쪽
        } else if(x == -depth){
            return startNumber + depth*3 - y;   //위쪽
        }
        return startNumber + depth  - x;    //오른쪽
    }

2번째 껍데기를 예로 들면,
오른쪽(10 ~ 12), 위(13 ~ 17), 왼쪽(18 ~ 20), 아래(21 ~ 25)로 나눌 수 있다.
그리고 숫자 좌표의 공통점을 찾을 수 있다.

오른쪽 숫자 좌표는 10(1,2), 11(0,2), 12(-1,2) : y값은 껍데기와 같고 x값은 줄어든다.
위쪽 숫자 좌표는 13(-2,2),14(-2,1),15(-2,0)... : -x값이 껍데기와 같고 y값은 줄어든다.
왼쪽 숫자 좌표는 17(-2,-2),18(-1,-2),19(0,-2)... : -y값이 껍데기와 같고 x값은 늘어난다.
아래쪽 숫자 좌표는 21(2,-2),22(2,-1),23(2,0)... : x값이 껍데기와 같고 y값은 늘어난다.

이 규칙에 따라서 spinalNumber를 구하는 코드를 짜면 된다.

💡내 코드

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int r1 = sc.nextInt();
        int c1 = sc.nextInt();
        int r2 = sc.nextInt();
        int c2 = sc.nextInt();
        int [][] map = new int[r2-r1+1][c2-c1+1];

        int maxNumber = 0;
        for (int i = r1; i <=r2 ; i++) {
            for (int j = c1; j <=c2 ; j++) {
                map[i-r1][j-c1] = spinalNumber(i,j);
                maxNumber = Math.max(maxNumber, map[i-r1][j-c1]);
            }
        }
        int maxLength = String.valueOf(maxNumber).length();

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < r2-r1+1; i++) {
            for (int j = 0; j < c2-c1+1; j++) {
                sb.append(String.format(""%""+maxLength+""d "", map[i][j]));
            }
            sb.setLength(sb.length()-1);
            sb.append(""\n"");
        }
        System.out.println(sb);
    }

    static int spinalNumber(int x, int y){
        int depth = Math.max(Math.abs(x), Math.abs(y));

        // 이전 depth의 마지막 수
        int startNumber = (2*depth-1)*(2*depth-1);

        if(x == depth){
            return startNumber + depth*7 + y;   //아래
        }else if(y == -depth){
            return startNumber + depth*5 + x;   //왼쪽
        } else if(x == -depth){
            return startNumber + depth*3 - y;   //위쪽
        }
        return startNumber + depth  - x;    //오른쪽
    }
}

• 소용돌이 좌표를 구하는 방법을 찾기 힘들었다.
• 종이에 숫자를 그려놓고 한참 헤맸다.
• 그래도 뿌듯하다!