[COS PRO 1급 기출문제] (1차) 5.소용돌이 수 (Java) - 구현/dp

생각의 흐름은 이러했다

→ 일단 배열만 만들면 구하는건 최대 n번 연산 안에 끝나니까 괜찮지 않을까 

→ 그래도 배열 만들기 전에 규칙성 있으면 활용하고 싶은데?

→ 규칙성 찾다가 포기, 일단 구현으로 해보자

→ 구현 후 규칙성 발견해 dp풀이

 

(1) 구현 (소용돌이 수 만들기)

소용돌이 수 배열을 만든 다음에 대각선의 합을 구하는 방식이다

class Main {
    public int solution(int n) {
        // 1. n x n 격자 생성
        int[][] grid = new int[n][n];
        
        // 2. 소용돌이 수 채우기
        int num = 1;
        int row = 0, col = 0;
        int[] dr = {0, 1, 0, -1}; 
        int[] dc = {1, 0, -1, 0};
        int dir = 0; 

			for (int i = 0; i < n * n; i++) {
            grid[row][col] = num++;
            
            if (i == n * n - 1) break; // 마지막 숫자
            
            // 다음 위치 계산
            int nextRow = row + dr[dir];
            int nextCol = col + dc[dir];
            
            // 방향 전환이 필요한 경우
            if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= n 
                || grid[nextRow][nextCol] != 0) {
                dir = (dir + 1) % 4; // 방향 전환
                nextRow = row + dr[dir];
                nextCol = col + dc[dir];
            }
            
            row = nextRow;
            col = nextCol;
        }
			 // 3. 대각선 합 구하기
        int answer = 0;
        for (int i = 0; i < n; i++) {
            answer += grid[i][i];
        }

        return answer;
    }

 

 

(2) dp 

격자는 크게 두 개로 나눌 수 있다 : 바깥 껍데기와 내부의 격자로

→ 내부의 격자는 한바퀴를 돌아 바깥 껍데기가 완성된 후에 채워지기 시작하므로, (바깥껍데기의 길이 + 1) 부터 시작한다

→ 내부 격자의 모든 값에서 이 (바깥 껍데기의 길이 + 1) 을 빼면, 1부터 시작하는 소용돌이 수가 된다

→ dp[n] = [바깥 껍데기의 양 끝 수] +  dp[n-2] + [바깥 층 크기 x 내부 격자 대각선 원소의 개수]

소용돌이 배열이 포함하고 있는 가장 큰 소용돌이 배열은 (4n-3) 부터 시작하는 소용돌이 배열

 

n=4 일떄를 예시로 보면 내부 격자에서 바깥 테두리 크기인 12를 빼면 1부터 시작하는 소용돌이 수임을 알 수 있다

class Main {
    public int solution(int n) {
        int[] dp = new int[n + 1];
        
        if (n >= 1) dp[1] = 1;
        if (n >= 2) dp[2] = 4;
        
        // DP 계산
        for (int i = 3; i <= n; i++) {
            int outer = 1 + (2 * i - 1);  // 바깥 층 양 끝
            int layerSize = 4 * i - 4;     // 바깥 층 크기
            int innerCount = i - 2;        // 안쪽 대각선 원소 개수
            
            dp[i] = outer + dp[i-2] + layerSize * innerCount;
        }
        
        return dp[n];
    }

 

dp 의 경우 뭔가 설명을 이거보다 더 잘할 수 있을거같은데 적절한 워딩이 생각이 안난다...